We consider the number of survivors in a broad class affair leader election algorithms after a number of election rounds. We give sufficient conditions for the number of survivors to converge to a product of independe...
详细信息
We consider the number of survivors in a broad class affair leader election algorithms after a number of election rounds. We give sufficient conditions for the number of survivors to converge to a product of independent identically distributed random variables. The number of terms in the product is determined by the round number considered. Each individual term in the product is a limit of a scaled random variable associated with the splitting protocol. The proof is established via convergence (to 0) of the first-order Wasserstein distance from the product limit. In a broader context, the paper is a case study of a class of stochastic recursive equations. We give two illustrative examples, one with binomial splitting protocol (for which we show that a normalized version is asymptotically Gaussian) and one with uniform splitting protocol. (C) 2013 Elsevier B.V. All rights reserved.
Let f : 2(N) -> Z(+) be a polymatroid (an integer-valued non-decreasing submodular set function with f(empty set) = 0). We call S (subset of) under bar N a base if f (S) = f (N). We consider the problern of finding...
详细信息
Let f : 2(N) -> Z(+) be a polymatroid (an integer-valued non-decreasing submodular set function with f(empty set) = 0). We call S (subset of) under bar N a base if f (S) = f (N). We consider the problern of finding, a maximum number of disjoint bases;we denote by m* be this base packing number. A simple upper bound on m* is given by k* = max{k : Sigma(i is an element of N)f(A)(i) >= kfa(N), for all A (subset of) under bar N) where f(A)(S) = f (A boolean OR S) - f (A). This upper bound is a natural generalization of the bound for matroids where it is known that m* = k* For polymatroids, we prove that m* >= (1 - o(1))k*/In f (N) and give a randomized polynomial time algorithm to find (1 - o(1))k*/In f (N) disjoint bases, assuming an oracle for f. We also derandomize the algorithm using minwise independent permutations and give a deterministic algorithm that finds (1 - is an element of)k*/In f(N) disjoint bases. The bound we obtain is almost tight because it is known there are polymatroids for which m* < (1 + o(1))k*/In f(N). Moreover it is known that unless NP <(subset of)under bar> DTIME(n(log log n)), for any is an element of > 0, there is no polynomial time algorithm to obtain a (1 + is an element of)/In f(N)-approximation to m*. Our result generalizes and unifies two results in the literature. (C) 2009 Wiley Periodicals, Inc. Random Struct. Alg., 35, 418-430, 2009
In this paper, a natural probabilistic model for motif discovery has been used to experimentally test the quality of motif discovery programs. In this model, there are k background sequences, and each character in a b...
详细信息
In this paper, a natural probabilistic model for motif discovery has been used to experimentally test the quality of motif discovery programs. In this model, there are k background sequences, and each character in a background sequence is a random character from an alphabet, Sigma. A motif G = g(1)g(2) center dot center dot center dot g(m) is a string of m characters. In each background sequence is implanted a probabilistically-generated approximate copy of G. For a probabilistically-generated approximate copy b(1)b(2) center dot center dot center dot b(m) of G, every character, b(i), is probabilistically generated, such that the probability for b(i) not equal = g(i) is at most alpha. We develop two new randomized algorithms and one new deterministic algorithm. They make advancements in the following aspects: (1) The algorithms are much faster than those before. Our algorithms can even run in sublinear time. (2) They can handle any motif pattern. (3) The restriction for the alphabet size is a lower bound of four. This gives them potential applications in practical problems, since gene sequences have an alphabet size of four. (4) All algorithms have rigorous proofs about their performances. The methods developed in this paper have been used in the software implementation. We observed some encouraging results that show improved performance for motif detection compared with other software.
This paper considers the following problem: given an edgeweighted graph G = (V, E, w) and disjoint k-subsets U-p of V, find a minimum weighted set of edges E' subset of E such that its removal disconnects the grap...
详细信息
This paper considers the following problem: given an edgeweighted graph G = (V, E, w) and disjoint k-subsets U-p of V, find a minimum weighted set of edges E' subset of E such that its removal disconnects the graph into k parts and each part contains exactly one vertex from each U-p for 1 <= p <= r. This generalizes some well-known NP-hard problems. In this paper, we first apply greedy local search algorithm to obtain better approximation solutions. Then we give a randomized local search algorithm which produces a solution within a factor (1 + epsilon) with the probability at least (1 - 1/e) for any small epsilon. Simple near- optimum approximation algorithms are also proposed. Analogously, there is a maximum k-multiway cut problem with the same restrictions.
Recently, Byrka, Grandoni, RothvoBand Sanita gave a 1.39 approximation for the Steiner tree problem, using a hypergraph-based linear programming relaxation. They also upper-bounded its integrality gap by 1.55. We desc...
详细信息
Recently, Byrka, Grandoni, RothvoBand Sanita gave a 1.39 approximation for the Steiner tree problem, using a hypergraph-based linear programming relaxation. They also upper-bounded its integrality gap by 1.55. We describe a shorter proof of the same integrality gap bound, by applying some of their techniques to a randomized loss-contracting algorithm. (C) 2010 Elsevier B.V. All rights reserved.
In this paper, a randomized parallel algorithm is proposed to solve the distributed optimal consensus problem of multi-agent systems. Involving both the transient response and the final consensus state, the problem is...
详细信息
In this paper, a randomized parallel algorithm is proposed to solve the distributed optimal consensus problem of multi-agent systems. Involving both the transient response and the final consensus state, the problem is described as a constrained non-separable optimization problem. Inspired by the randomized Jacobi proximal alternating direction method of multipliers, the proposed algorithm makes it possible for only a fraction of agents to solve their private subproblems in parallel at each iteration, which greatly saves computational resources and enhances running efficiency. The convergence analysis of the algorithm gives fully distributed convergence conditions. A trade-off between the convergence speed and resource savings is then obtained, where the convergence rate is estimated to be at least O (1 ). Furthermore, the algorithm can be accelerated to enjoy a convergence ( 1 ) t rate of O t2 by adaptively adjusting the auxiliary parameters properly. Numerical simulations demonstrate the effectiveness of the theoretical results.
Functional data analysis (FDA) methods have computational and theoretical appeals for some high dimensional data, but lack the scalability to modern large sample datasets. To tackle the challenge, we develop randomize...
详细信息
Functional data analysis (FDA) methods have computational and theoretical appeals for some high dimensional data, but lack the scalability to modern large sample datasets. To tackle the challenge, we develop randomized algorithms for two important FDA methods: functional principal component analysis (FPCA) and functional linear regression (FLR) with scalar response. The two methods are connected as they both rely on the accurate estimation of functional principal subspace. The proposed algorithms draw subsamples from the large dataset at hand and apply FPCA or FLR over the subsamples to reduce the computational cost. To effectively preserve subspace information in the subsamples, we propose a functional principal subspace sampling probability, which removes the eigenvalue scale effect inside the functional principal subspace and properly weights the residual. Based on the operator perturbation analysis, we show the proposed probability has precise control over the first order error of the subspace projection operator and can be interpreted as an importance sampling for functional subspace estimation. Moreover, concentration bounds for the proposed algorithms are established to reflect the low intrinsic dimension nature of functional data in an infinite dimensional space. The effectiveness of the proposed algorithms is demonstrated upon synthetic and real datasets.
This paper gives various (positive and negative) results on the complexity of the problem of computing and approximating mixed volumes of polytopes and more general convex bodies in arbitrary dimension. On the negativ...
详细信息
This paper gives various (positive and negative) results on the complexity of the problem of computing and approximating mixed volumes of polytopes and more general convex bodies in arbitrary dimension. On the negative side, we present several # P-hardness results that focus on the difference of computing mixed volumes versus computing the volume of polytopes. We show that computing the volume of zonotopes is # P-hard (while each corresponding mixed volume can be computed easily) but also give examples showing that computing mixed volumes is hard even when computing the volume is easy. On the positive side, we derive a randomized algorithm for computing the mixed volumes [GRAPHICS] of well-presented convex bodies K(1),...,K(s), where m(1),...,m(s) is an element of N(0) and m(1) greater than or equal to n - psi(n) with psi(n) = o(log n/log log n). The algorithm is an interpolation method based on polynomial-time randomized log algorithms for computing the volume of convex bodies. This paper concludes with applications of our results to various problems in discrete mathematics, combinatorics, computational convexity, algebraic geometry, geometry of numbers, and operations research.
Most prior work in leader election algorithms deals with univariate statistics. We consider multivariate issues in a broad class of fair leader election algorithms. We investigate the joint distribution of the duratio...
详细信息
Most prior work in leader election algorithms deals with univariate statistics. We consider multivariate issues in a broad class of fair leader election algorithms. We investigate the joint distribution of the duration of two competing candidates. Under rather mild conditions on the splitting protocol, we prove the convergence of the joint distribution of the duration of any two contestants to a limit via convergence of distance (to 0) in a metric space on distributions. We then show that the limiting distribution is a Marshall-Olkin bivariate geometric distribution. Under the classic binomial splitting we are able to say a few more precise words about the exact joint distribution and exact covariance, and to explore (via Rice's integral method) the oscillatory behavior of the diminishing covariance. We discuss several practical examples and present empirical observations on the rate of convergence of the covariance.
Low rank approximation of matrices has been well studied in literature. Singular value decomposition, QR decomposition with column pivoting, rank revealing QR factorization, Interpolative decomposition, etc. are class...
详细信息
Low rank approximation of matrices has been well studied in literature. Singular value decomposition, QR decomposition with column pivoting, rank revealing QR factorization, Interpolative decomposition, etc. are classical deterministic algorithms for low rank approximation. But these techniques are very expensive ( operations are required for matrices). There are several randomized algorithms available in the literature which are not so expensive as the classical techniques (but the complexity is not linear in n). So, it is very expensive to construct the low rank approximation of a matrix if the dimension of the matrix is very large. There are alternative techniques like Cross/Skeleton approximation which gives the low-rank approximation with linear complexity in n. In this article we review low rank approximation techniques briefly and give extensive references of many techniques.
暂无评论