The worst-case complexity of an implementation of Quicksort depends on the random source that is used to select the pivot elements. In this paper we estimate the expected number of comparisons of Quicksort as a functi...
详细信息
ISBN:
(纸本)3540280618
The worst-case complexity of an implementation of Quicksort depends on the random source that is used to select the pivot elements. In this paper we estimate the expected number of comparisons of Quicksort as a function of the entropy of the random source. We give upper and lower bounds and show that the expected number of comparisons increases from n log n to n(2), if the entropy of the random source is bounded. As examples we show explicit bounds for distributions with bounded min-entropy and the geometrical distribution, as well as an upper bound when using a delta-random source.
A problem for many kernel-based methods is that the amount of computation required to find the solution scales as O(n(3)), where n is the number of training examples. We develop and analyze an algorithm to compute an ...
详细信息
A problem for many kernel-based methods is that the amount of computation required to find the solution scales as O(n(3)), where n is the number of training examples. We develop and analyze an algorithm to compute an easily-interpretable low-rank approximation to an n x n Gram matrix G such that computations of interest may be performed more rapidly. The approximation is of the form (G) over tilde (k) = CWk+ C-T, where C is a matrix consisting of a small number c of columns of G and W-k is the best rank-k approximation to W, the matrix formed by the intersection between those c columns of G and the corresponding c rows of G. An important aspect of the algorithm is the probability distribution used to randomly sample the columns;we will use a judiciously-chosen and data-dependent nonuniform probability distribution. Let parallel to(.)parallel to(2) and parallel to(.)parallel to(F) denote the spectral norm and the Frobenius norm, respectively, of a matrix, and let G(k) be the best rank-k approximation to G. We prove that by choosing O(k/epsilon(4)) columns parallel to G-(CWk+CT)parallel to(xi) <=parallel to G-G(k)parallel to(xi)+epsilon Sigma(n)(i=1) G(ii)(2) both in expectation and with high probability, for both xi = 2, F, and for all k : 0 <= k <= rank(W). This approximation can be computed using O(n) additional space and time, after making two passes over the data from external storage. The relationships between this algorithm, other related matrix decompositions, and the Nystrom method from integral equation theory are discussed.
We present an O(n(3))-time approximation algorithm for the maximum traveling salesman problem whose approximation ratio is asymptotically 61/81, where n is the number of vertices in the input complete edge-weighted (u...
详细信息
We present an O(n(3))-time approximation algorithm for the maximum traveling salesman problem whose approximation ratio is asymptotically 61/81, where n is the number of vertices in the input complete edge-weighted (undirected) graph. We also present an O(n(3))-time approximation algorithm for the metric case of the problem whose approximation ratio is asymptotically 17/20. Both algorithms improve on the previous bests. (c) 2005 Elsevier B.V. All rights reserved.
This paper considers probabilistic robust control of nonlinear uncertain systems. A combination of stochastic robustness and dynamic inversion is proposed for general systems that have a feedback-linearizable nominal ...
详细信息
This paper considers probabilistic robust control of nonlinear uncertain systems. A combination of stochastic robustness and dynamic inversion is proposed for general systems that have a feedback-linearizable nominal system. In this paper, the stochastic robust nonlinear control approach is applied to a highly nonlinear complex aircraft model, the high-incidence research model (HIRM). The model addresses a high-angle-of-attack enhanced manual control problem. The aim of the flight control system is to give good handling qualities across the specified flight envelope without the use of gain scheduling and also to provide robustness to modeling uncertainties. The proposed stochastic robust nonlinear control explores the direct design of nonlinear flight control logic. Therefore, the final design accounts for all significant nonlinearities in the aircraft's high-fidelity simulation model. The controller parameters are designed to minimize the probability of violating design specifications, which provides the design with good robustness in stability and performance subject to modeling uncertainties. The present design compares favorably with earlier controllers that were generated for a benchmark design competition.
A basic problem in graphs and hypergraphs is that of finding a large independent set-one of guaranteed size. Understanding the parallel complexity of this and related independent set problems on hypergraphs is a funda...
详细信息
A basic problem in graphs and hypergraphs is that of finding a large independent set-one of guaranteed size. Understanding the parallel complexity of this and related independent set problems on hypergraphs is a fundamental open issue in parallel computation. Caro and Tuza [J. Graph Theory, 15 (1991), pp. 99-107] have shown a certain lower bound alpha(k)(H) on the size of a maximum independent set in a given k-uniform hypergraph H and have also presented an efficient sequential algorithm to find an independent set of size alpha k(H). They also show that alpha(k)(H) is the size of the maximum independent set for various hypergraph families. Here, we show that an RNC algorithm due to Beame and Luby [in Proceedings of the ACM-SIAM Symposium on Discrete algorithms, 1990, pp. 212-218] finds an independent set of expected size alpha(k)(H) and also derandomizes it for certain special cases. (An intriguing conjecture of Beame and Luby implies that understanding this algorithm better may yield an RNC algorithm to find a maximal independent set in hypergraphs, which is among the outstanding open questions in parallel computation.) We also present lower bounds on independent set size for nonuniform hypergraphs using this algorithm. For graphs, we get an NC algorithm to find independent sets of size essentially that guaranteed by the general (degree-sequence based) version of Turan's theorem.
Our first contribution is a substantial acceleration of randomized computation of scalar, univariate, and multivariate matrix determinants, in terms of the output-sensitive bit operation complexity bounds, including c...
详细信息
Our first contribution is a substantial acceleration of randomized computation of scalar, univariate, and multivariate matrix determinants, in terms of the output-sensitive bit operation complexity bounds, including computation modulo a product of random primes from a fixed range. This acceleration is dramatic in a critical application, namely solving polynomial systems and related studies, via computing the resultant. This is achieved by combining our techniques with the primitive-element method, which leads to an effective implicit representation of the roots. We systematically examine quotient formulae of Sylvester-type resultant matrices, including matrix polynomials and the u-resultant. We reduce the known bit operation complexity bounds by almost an order of magnitude, in terms of the resultant matrix dimension. Our theoretical and practical improvements cover the highly important cases of sparse and degenerate systems. (C) 2004 Elsevier Inc. All rights reserved.
In this paper we give a very space-efficient, yet fast method for estimating the fractal dimensionality of the points in a data stream. algorithms to estimate the fractal dimension exist, such as the straightforward q...
详细信息
In this paper we give a very space-efficient, yet fast method for estimating the fractal dimensionality of the points in a data stream. algorithms to estimate the fractal dimension exist, such as the straightforward quadratic algorithm and the faster O(N log N) or even O(N) box-counting algorithms. However, the sub-quadratic algorithms require Omega(N) space. In this paper, we propose an algorithm that computes the fractal dimension in a single pass, using a constant amount of memory relative to data cardinality. Experimental results on synthetic and real world data sets demonstrate the effectiveness of our algorithm. (C) 2004 Elsevier B.V. All rights reserved.
Partitioned optical passive stars (POPS) network has been proposed recently as a desirable model of parallel computing. Many papers have been published that address fundamental problems on these networks. Packet routi...
详细信息
Partitioned optical passive stars (POPS) network has been proposed recently as a desirable model of parallel computing. Many papers have been published that address fundamental problems on these networks. Packet routing is one such important problem. We present a randomized algorithm in this paper that performs better than the best prior algorithms. We also present a randomized algorithm for selection on the POPS network. (c) 2005 Elsevier Inc. All rights reserved.
Combinatorial property testing, initiated formally by Goldreich, Goldwasser, and Ron (1998) and inspired by Rubinfeld and Sudan (1996), deals with the relaxation of decision problems. Given a property P the aim is to ...
详细信息
Combinatorial property testing, initiated formally by Goldreich, Goldwasser, and Ron (1998) and inspired by Rubinfeld and Sudan (1996), deals with the relaxation of decision problems. Given a property P the aim is to decide whether a given input satisfies the property P or is far from having the property. For a family of boolean functions f = (f(n)) the associated property is the set of 1-inputs of f. Here, the known lower bounds on the query complexity of properties identified by boolean functions representable by (very) restricted branching programs of small size is improved up to Omega(n(1/2)), where n is the input length. (c) 2005 Elsevier B.V. All rights reserved.
Herman's Ring [Inform. Process. Lett. 35 (1990) 63;http://***/ftp/selfstab/***] is an algorithm for self-stabilization of N identical processors connected uni-directionally in a synchronous ring;in its original fo...
详细信息
Herman's Ring [Inform. Process. Lett. 35 (1990) 63;http://***/ftp/selfstab/***] is an algorithm for self-stabilization of N identical processors connected uni-directionally in a synchronous ring;in its original form it has been shown to achieve stabilization, with probability one, in expected steps O (N-2 log N). We give an elementary proof that the original algorithm is in fact O(N-2);and for the special case of three tokens initially we give an exact (quadratic) solution of 4abc/N, where a, b, c are the tokens' initial separations. Thus the algorithm overall has worst-case expected running time of Theta(N-2). Although we use only simple matrix algebra in the proof, the approach was suggested by the general notions of abstraction, nondeterminism and probabilistic variants [A. McIver, C. Morgan, Refinement and Proof for Probabilistic Systems, Technical Monographs in Computer Science, Springer-Verlag, New York, 2004]. It is hoped they could also be useful for other, similar problems. We conclude with an open problem concerning the worst-case analysis. (c) 2005 Elsevier B.V. All rights reserved.
暂无评论