Optimal Threshold for the k-Out-Of-n Monitor with Dual Failure Modes

A monitor consists of n identical sensors working independently. Each sensor measures a variate of output or environment of a system, and is activated if a variate is over a threshold specified in advance for each sensor. The monitor alarms if at least k out of n sensors are activated. The performance of the monitor, the probabilities of failure to alarm and false alarming, depends on the number k, the threshold values and the probability distributions of the variate at normal and abnormal states of the system. In this paper, a sufficient condition on the pair of the distributions is given under which the same threshold values for all the sensors are optimal. The condition motivates new orders between probability distributions. Solving an optimization problem an explicit condition is obtained for maximizing or minimizing a symmetric function with the constraint of another symmetric function.     

The Distributedk-Server Problem—A Competitive Distributed Translator fork-Server Algorithms

We consider thek-server problem23in a distributed setting. Given a network ofnprocessors andkidentical mobile servers, requests for service appear at the processors and a server must reach the request point. In addition to modeling problems in computer networks wherekidentical mobile resources are shared by the processors of the network, this models a realistic situation where the transfer of information is costly and there is no central control that governs the behavior of servers that move around to satisfy requests for service. We give a general translator to transform any deterministic global-control competitivek-server algorithm into a distributed competitive one. As consequences we get poly(k)-competitive distributed algorithms for the line, trees, and the ring. In contrast to the global-control case where there arek-server algorithms with competitive ratio that depends solely onk, we have a lower bound of Ω(max{k, (1/D) ·(log n/log log n)}) on the competitive ratio of any distributedk-server algorithm, where 1/Dis the ratio between the cost to transmit a message and the cost to move a server over the same distance. We also give a distributed version of the Harmonic randomizedk-server algorithm.     

The structure of 4‐strong tournaments containing exactly three out‐arc pancyclic vertices

Yao et al. (Discrete Appl Math 99 (2000), 245–249) proved that every strong tournament contains a vertex u such that every out‐arc of u is pancyclic and conjectured that every k‐strong tournament contains k such vertices. At present, it is known that this conjecture is true for k = 1, 2, 3 and not true for k?4. In this article, we obtain a sufficient and necessary condition for a 4‐strong tournament to contain exactly three out‐arc pancyclic vertices, which shows that a 4‐strong tournament contains at least four out‐arc pancyclic vertices except for a given class of tournaments. Furthermore, our proof yields a polynomial algorithm to decide if a 4‐strong tournament has exactly three out‐arc pancyclic vertices.     

Torpid mixing of the Wang–Swendsen–Kotecký algorithm for sampling colorings

We study the problem of sampling uniformly at random from the set of k-colorings of a graph with maximum degree Δ. We focus attention on the Markov chain Monte Carlo method, particularly on a popular Markov chain for this problem, the Wang–Swendsen–Kotecký (WSK) algorithm. The second author recently proved that the WSK algorithm quickly converges to the desired distribution when k11Δ/6. We study how far these positive results can be extended in general. In this note we prove the first non-trivial results on when the WSK algorithm takes exponentially long to reach the stationary distribution and is thus called torpidly mixing. In particular, we show that the WSK algorithm is torpidly mixing on a family of bipartite graphs when 3k<Δ/(20logΔ), and on a family of planar graphs for any number of colors. We also give a family of graphs for which, despite their small chromatic number, the WSK algorithm is not ergodic when kΔ/2, provided k is larger than some absolute constant k₀.     

Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing

We study the average case performance of the Best Fit algorithm for on-line bin packing under the distributionU{j, k}, in which the item sizes are uniformly distributed in the discrete range {1/k, 2/k,…,j/k}. Our main result is that, in the casej = k − 2, the expected waste for an infinite stream of items remains bounded. This settles an open problem posed by Coffmanet al.[[4]]. It is also the first result which involves a detailed analysis of the infinite multidimensional Markov chain underlying the algorithm.     

A large closed queueing network with autonomous service and bottleneck

This paper studies the queue-length process in a closed Jackson-type queueing network with the large number N of homogeneous customers by methods of the theory of martingales and by the up- and down-crossing method. The network considered here consists of a central node (hub), being an infinite-server queueing system with exponentially distributed service times, and k single-server satellite stations (nodes) with generally distributed service times with rates depending on the value N. The service mechanism of these k satellite stations is autonomous, i.e., every satellite server j serves the customers only at random instants that form a strictly stationary and ergodic sequence of random variables. Assuming that the first k-1 satellite stations operate in light usage regime the paper considers the cases where the kth satellite station is a bottleneck node. The approach of the paper is based both on development of the method from the paper by Kogan and Liptser [16], where a Markovian version of this model has been studied, and on development of the up- and down-crossing method. This revised version was published online in June 2006 with corrections to the Cover Date.     

Shifted tableaux,schur Q-functions,and a conjecture of R. Stanley

We present an analog of the Robinson-Schensted correspondence that applies to shifted Young tableaux and is considerably simpler than the one proposed in [B. E. Sagan, J. Combin. Theory Ser. A 27 (1979), 10–18]. In addition, this algorithm enjoys many of the important properties of the original Robinson-Schensted map including an interpretation of row lengths in terms of k-increasing sequences, a jeu de taquin, and a generalization to tableaux with repeated entries analogous to Knuth's construction (Pacific J. Math. 34 (1970), 709–727). The fact that the Knuth relations hold for our algorithm yields a simple proof of a conjecture of Stanley.     

A proof of Parisi’s conjecture on the random assignment problem

An assignment problem is the optimization problem of finding, in an m by n matrix of nonnegative real numbers, k entries, no two in the same row or column, such that their sum is minimal. Such an optimization problem is called a random assignment problem if the matrix entries are random variables. We give a formula for the expected value of the optimal k-assignment in a matrix where some of the entries are zero, and all other entries are independent exponentially distributed random variables with mean 1. Thereby we prove the formula 1+1/4+1/9+...+1/k ² conjectured by G. Parisi for the case k=m=n, and the generalized conjecture of D. Coppersmith and G. B. Sorkin for arbitrary k, m and n. AcknowledgementWe thank Mireille Bousquet-Mélou and Gilles Schaeffer for introducing the problem to us. We also thank an anonymous referee for suggesting some improvements of the exposition.     

Properties of the nonsymmetric Robinson–Schensted–Knuth algorithm

We introduce a generalization of the Robinson–Schensted–Knuth insertion algorithm for semi-standard augmented fillings whose basement is an arbitrary permutation σ∈S _n . If σ is the identity, then our insertion algorithm reduces to the insertion algorithm introduced by the second author (Sémin. Lothar. Comb. 57:B57e, 2006) for semi-standard augmented fillings and if σ is the reverse of the identity, then our insertion algorithm reduces to the original Robinson–Schensted–Knuth row insertion algorithm. We use our generalized insertion algorithm to obtain new decompositions of the Schur functions into nonsymmetric elements called generalized Demazure atoms (which become Demazure atoms when σ is the identity). Other applications include Pieri rules for multiplying a generalized Demazure atom by a complete homogeneous symmetric function or an elementary symmetric function, a generalization of Knuth’s correspondence between matrices of non-negative integers and pairs of tableaux, and a version of evacuation for composition tableaux whose basement is an arbitrary permutation σ.     

Reliability of ak-out-of-n system with repair and retrial of failed units

We consider ak-out-of-n system with repair. Life times of components are independent exponentially distributed random variables with parameter λ _i when the number of working units isi. Failed units are taken for repair to a station, manned by a single server, having no waiting room. The failed units are brought to an orbit, if the server is found to be busy, for retrial. Reliability of the system is computed in the following three situations: (i) Cold system (ii) Warm system and (iii) Hot system. Several other system characteristics are derived.     

k-out-of-n-system with repair:T-policy

We consider a k-out-of-n system with repair underT-policy. Life time of each component is exponentially distributed with parameter λ. Server is called to the system after the elapse ofT time units since his departure after completion of repair of all failed units in the previous cycle or until accumulation ofn — k failed units, whichever occurs first. Service time is assumed to be exponential with rateμ.T is also exponentially distributed with parameter α. System state probabilities in finite time and long run are derived for (i) cold (ii) warm (iii) hot systems. Several characteristics of these systems are obtained. A control problem is also investigated and numerical illustrations are provided. It is proved that the expected profit to the system is concave in α and hence global maximum exists.     

Existence of a limiting distribution for the binary GCD algorithm

In this article, we prove the existence and uniqueness of a certain distribution function on the unit interval. This distribution appears in Brent's model of the analysis of the binary gcd algorithm. The existence and uniqueness of such a function was conjectured by Richard Brent in his original paper [R.P. Brent, Analysis of the binary Euclidean algorithm, in: J.F. Traub (Ed.), New Directions and Recent Results in Algorithms and Complexity, Academic Press, New York, 1976, pp. 321–355]. Donald Knuth also supposes its existence in [D.E. Knuth, The Art of Computer Programming, vol. 2, Seminumerical Algorithms, third ed., Addison-Wesley, Reading, MA, 1997] where developments of its properties lead to very good estimates in relation to the algorithm. We settle here the question of existence, giving a basis to these results, and study the relationship between this limiting function and the binary Euclidean operator B₂, proving rigorously that its derivative is a fixed point of B₂.     

A parametric <Emphasis Type="Italic">k</Emphasis>-means algorithm

The k points that optimally represent a distribution (usually in terms of a squared error loss) are called the k principal points. This paper presents a computationally intensive method that automatically determines the principal points of a parametric distribution. Cluster means from the k-means algorithm are nonparametric estimators of principal points. A parametric k-means approach is introduced for estimating principal points by running the k-means algorithm on a very large simulated data set from a distribution whose parameters are estimated using maximum likelihood. Theoretical and simulation results are presented comparing the parametric k-means algorithm to the usual k-means algorithm and an example on determining sizes of gas masks is used to illustrate the parametric k-means algorithm.     

Diagnostics on LALR(k) conflicts based on a method for LR(k) Testing

A user of an LALR(k) parser generator system may have difficulties in understanding how a given LALR(k) conflict is generated. This is especially difficult if the conflict does not correspond to an LR(k) conflict.A practical method for giving informative diagnostics on LALR(k) conflicts is presented. The diagnostics distinguish between those LALR(k) conflicts that correspond to LR(k) conflicts and those that do not. As a side effect the user is thus informed whether or not his grammar is in fact LR(k) despite not being LALR(k).The method is based on an algorithm for testing LR(k)-ness using the LR(0) machine supplied with LALR(k) lookahead sets. This algorithm is presented and its correctness is proved.     

Some mixing properties of tukey's 3R smoother †

Suppose Tukey's 3R (“running median”) smoothing algorithm is applied to a strictly stationary sequence X: = (X_k) of random variables, thereby creating a new stationary sequence X? If X satisfies the strong (Rosenblatt) mixing condition, then so does .X? If X is an i.i.d. sequence with each X(_k:) uniformly distributed on the interval [0,1], then X? fails to be (mixing. Thus two questions of C. Mallows are answered.     

Efficient algorithms for a constrained k-tree core problem in a tree network

Let T=(V,E) be a free tree in which each vertex has a weight and each edge has a length. Let n=|V|. Given T and parameters k and l, a (k,l)-tree core is a subtree X of T with diameter l, having k leaves, which minimizes the sum of the weighted distances from all vertices in T to X. In this paper, two efficient algorithms are presented for finding a (k,l)-tree core of T. The first algorithm has O(n²) time complexity for the case that each edge has an arbitrary length. The second algorithm has O(lkn) time complexity for the case that the lengths of all edges are 1. The (k,l)-tree core problem has an application in distributed database systems.     

Approximation Algorithms for Dispersion Problems

Given a collection of weighted sets, each containing at most k elements drawn from a finite base set, the k-set packing problem is to find a maximum weight sub-collection of disjoint sets. A greedy algorithm for this problem approximates it to within a factor of k, and a natural local search has been shown to approximate it to within a factor of roughly k − 1. However, neither paradigm can yield approximations that improve on this.We present an approximation algorithm for the weighted k-set packing problem that combines the two paradigms by starting with an initial greedy solution and then repeatedly choosing the best possible local improvement. The algorithm has a performance ratio of 2(k + 1)/3, which we show is asymptotically tight. This is the first asymptotic improvement over the straightforward ratio of k.     

Some Results for Large Closed Queueing Networks with and without Bottleneck: Up- and Down-Crossings Approach

The paper provides the up- and down-crossing method to study the asymptotic behavior of queue-length and waiting time in closed Jackson-type queueing networks. These queueing networks consist of central node (hub) and k single-server satellite stations. The case of infinite server hub with exponentially distributed service times is considered in the first section to demonstrate the up- and down-crossing approach to such kind of problems and help to understand the readers the main idea of the method. The main results of the paper are related to the case of single-server hub with generally distributed service times depending on queue-length. Assuming that the first k–1 satellite nodes operate in light usage regime, we consider three cases concerning the kth satellite node. They are the light usage regime and limiting cases for the moderate usage regime and heavy usage regime. The results related to light usage regime show that, as the number of customers in network increases to infinity, the network is decomposed to independent single-server queueing systems. In the limiting cases of moderate usage regime, the diffusion approximations of queue-length and waiting time processes are obtained. In the case of heavy usage regime it is shown that the joint limiting non-stationary queue-lengths distribution at the first k–1 satellite nodes is represented in the product form and coincides with the product of stationary GI/M/1 queue-length distributions with parameters depending on time.     

Triangulating Smooth Submanifolds with Light Scaffolding

We propose an algorithm to sample and mesh a k-submanifold M{\mathcal{M}} of positive reach embedded in \mathbbR^d{\mathbb{R}^{d}} . The algorithm first constructs a crude sample of M{\mathcal{M}} . It then refines the sample according to a prescribed parameter e{\varepsilon} , and builds a mesh that approximates M{\mathcal{M}} . Differently from most algorithms that have been developed for meshing surfaces of \mathbbR ³{\mathbb{R} ^3} , the refinement phase does not rely on a subdivision of \mathbbR ^d{\mathbb{R} ^d} (such as a grid or a triangulation of the sample points) since the size of such scaffoldings depends exponentially on the ambient dimension d. Instead, we only compute local stars consisting of k-dimensional simplices around each sample point. By refining the sample, we can ensure that all stars become coherent leading to a k-dimensional triangulated manifold [^(M)]{\hat{\mathcal{M}}} . The algorithm uses only simple numerical operations. We show that the size of the sample is O(e^-k){O(\varepsilon ^{-k})} and that [^(M)]{\hat{\mathcal{M}}} is a good triangulation of M{\mathcal{M}} . More specifically, we show that M{\mathcal{M}} and [^(M)]{\hat{\mathcal{M}}} are isotopic, that their Hausdorff distance is O(e²){O(\varepsilon ^{2})} and that the maximum angle between their tangent bundles is O(e){O(\varepsilon )} . The asymptotic complexity of the algorithm is T(e) = O(e^-k2-k){T(\varepsilon) = O(\varepsilon ^{-k^2-k})} (for fixed M, d{\mathcal{M}, d} and k).     

On the Law of The Iterated Logarithm for Rapidly Increasing Subsequences

The usual law of the iterated logarithm states that the partial sums S_n of independent and identically distributed random variables can be normalized by the sequence a_n = √nlog log n, such that limsup_n→∞ S_n/a_n = √2 a.s. As has been pointed out by Gut (1986) the law fails if one considers the limsup along subsequences which increase faster than exponentially. In particular, for very rapidly increasing subsequences {n_k≥1} one has limsup_k→∞ S_nk/a_nk = 0 a.s. In these cases the normalizing constants a_nk have to be replaced by √nk log k to obtain a non-trivial limiting behaviour: limsup_k→∞ S_nk/ √nk log k = √2 a.s. We will present an intelligible argument for this structural change and apply it to related results.