The so-called Maximum Clique Problem is one of the most famous NP-complete problems for which it is difficult to find a solution. Given an indirected graph, we present here a polynomial-time randomized algorithm RaCLI...
详细信息
The so-called Maximum Clique Problem is one of the most famous NP-complete problems for which it is difficult to find a solution. Given an indirected graph, we present here a polynomial-time randomized algorithm RaCLIQUE for finding a near-maximum clique. While the basic idea of the algorithm comes from Boltzmann machines, it employs no simulated annealing at all and hence it is simple to control its execution. We have confirmed in experiments for several random and nonrandom graphs with up to 400 nodes that very good solutions can be found efficiently compared with the other conventional algorithms.
randomized algorithms in numerical linear algebra can be fast, scalable and robust. This paper examines the effect of sketching on the right singular vectors corresponding to the smallest singular values of a tall-ski...
详细信息
randomized algorithms in numerical linear algebra can be fast, scalable and robust. This paper examines the effect of sketching on the right singular vectors corresponding to the smallest singular values of a tall-skinny matrix. We analyze a fast algorithm by Gilbert, Park andWakin for finding the trailing right singular vectors using randomization by examining the quality of the solution using multiplicative perturbation theory. For an m x n (m >= n) matrix, the algorithm runs with complexity O(mn log n + n(3)) which is faster than the standard O(mn(2)) methods. In applications, numerical experiments show great speedups including a 30x speedup for the AAA algorithm and 10x speedup for the total least squares problem.
Given an edge-weighted complete graph G on 3n vertices, the maximum-weight triangle packing problem asks for a collection of n vertex-disjoint triangles in G such that the total weight of edges in these n triangles is...
详细信息
Given an edge-weighted complete graph G on 3n vertices, the maximum-weight triangle packing problem asks for a collection of n vertex-disjoint triangles in G such that the total weight of edges in these n triangles is maximized. Although the problem has been extensively studied in the literature, it is surprising that prior to this work, no nontrivial approximation algorithm had been designed and analyzed for its metric case, where the edge weights in the input graph satisfy the triangle inequality. In this paper, we design the first nontrivial polynomial-time approximation algorithm for the maximum-weight metric triangle packing problem. Our algorithm is randomized and achieves an expected approximation ratio of 0.66768 - epsilon for any constant epsilon > 0.
In this paper, we study the minimum-latency broadcast scheduling problem in the probabilistic model. We establish an explicit relationship between the tolerated transmission-failure probability and the latency of the ...
详细信息
In this paper, we study the minimum-latency broadcast scheduling problem in the probabilistic model. We establish an explicit relationship between the tolerated transmission-failure probability and the latency of the corresponding broadcast schedule. Such a tolerated transmission-failure probability is calculated in the strict sense that the failure to receive the message at any single node will lead to the entire broadcast failure and only if all nodes have successfully received the message do we consider it a success. We design a novel broadcast scheduling algorithm such that the broadcast latency is evaluated under such a strict definition of failure. The latency bound we derive is a strong result in the sense that our algorithm achieves a low broadcast latency under this rather strict broadcast-failure definition. Simulation results are also provided to justify our derived theoretical latency bound.
The results of a parallel implementation of a randomized vector algorithm for solving systems of linear equations are presented in the paper. The solution is represented in the form of a Neumann series. The stochastic...
详细信息
The results of a parallel implementation of a randomized vector algorithm for solving systems of linear equations are presented in the paper. The solution is represented in the form of a Neumann series. The stochastic method computes this series by sampling only random columns, avoiding multiplication of matrix by matrix and matrix by vector. We consider the case when the matrix is too large to fit in randomaccess memory (RAM). We use two approaches to solve this problem. In the first approach, the matrix is divided into parts that are distributed among MPI processes and stored in the available RAM of the cluster nodes. In the second approach, the entire matrix is stored on each node's hard drive, loaded into RAM, and processed in parts. Independent Monte Carlo experiments for random column indices are distributed among MPI processes or OpenMP threads for both approaches to matrix storage. The efficiency of parallel implementations is analyzed. Results are given for a system governed by dense matrices of size 10(4) and 10(5).
A simple parallel randomized algorithm to find a maximal matching is developed. It is randomized in that it uses randomly chosen numbers. Its characteristics and efficiency do not depend upon the assumption that the...
详细信息
A simple parallel randomized algorithm to find a maximal matching is developed. It is randomized in that it uses randomly chosen numbers. Its characteristics and efficiency do not depend upon the assumption that the input graph is random. A basic operation of the algorithm is a random choice operation (RCO) involving a nonzero boolean vector. The expected time complexity of the algorithm is proven, leading to a trivial implementation of the algorithm on an EREW-PRAM. It is then shown how to perform RCO in the expected time on a CRCW-PRAM, which yields the promised complexity. The expected time is independent of the input graph's structure; this improves the best known deterministic algorithm.
Given n points in the plane and an integer k, 1 less-than-or-equal-to k less-than-or-equal-to (2n), we want to select the pair of points determining the line with the kth smallest slope. An optimal O(n log n) determin...
详细信息
Given n points in the plane and an integer k, 1 less-than-or-equal-to k less-than-or-equal-to (2n), we want to select the pair of points determining the line with the kth smallest slope. An optimal O(n log n) deterministic algorithm for this problem was given by Cole, Salowe, Steiger and Szemeredi;their algorithm is quite involved. Here we give a very simple randomized algorithm with O(n log n) expected running time. We also outline other possible applications of the technique.
作者：
Miyazawa, HErlebach, TETH
Comp Engn & Networks Lab TIK CH-8092 Zurich Switzerland Univ Tokyo
Grad Sch Engn Dept Math Engn & Informat Phys Bunkyo Ku Tokyo 1138656 Japan
Given a set of weighted intervals, the objective of the weighted interval selection problem (WISP) is to select a maximum-weight subset such that the selected intervals are pairwise disjoint. We consider on-line algor...
详细信息
Given a set of weighted intervals, the objective of the weighted interval selection problem (WISP) is to select a maximum-weight subset such that the selected intervals are pairwise disjoint. We consider on-line algorithms that process the intervals in order of non-decreasing left endpoints. Preemption is allowed, but rejections are irrevocable. This problem has natural applications in various scheduling problems. We study the class of monotone instances of WISP, i.e., we require that the order of right endpoints of the given intervals coincides with that of the left endpoints. This class includes the case where all intervals have the same length. For monotone instances of WISP, the best possible competitive ratio for deterministic on-line algorithms is known to be 1/4. It has long been an open question whether there exists a randomized algorithm with better competitive ratio. In this paper, we present a new randomized algorithm and prove that it achieves a better competitive ratio 1/3 for the special case of monotone WISP where the sequence of weights of the arriving intervals is non-decreasing. Thus we provide the first result towards a solution of the long-standing open question. Furthermore, we show that no randomized algorithm achieves a competitive ratio strictly larger than 4/5. This is the first non-trivial upper bound for randomized algorithms for monotone WISP.
In this paper we propose and analyze a randomized algorithm to get rendezvous between neighbours in an anonymous graph. We examine in particular the probability to obtain at least one rendezvous and the expected numbe...
详细信息
In this paper we propose and analyze a randomized algorithm to get rendezvous between neighbours in an anonymous graph. We examine in particular the probability to obtain at least one rendezvous and the expected number of rendezvous. We study the rendezvous number distribution in the cases of chain graphs, rings, and complete graphs. The last part is devoted to the efficiency of the proposed algorithm. (C) 2003 Elsevier Science (USA). All rights reserved.
This manuscript describes a technique for computing partial rank-revealing factorizations, such as a partial QR factorization or a partial singular value decomposition. The method takes as input a tolerance epsilon an...
详细信息
This manuscript describes a technique for computing partial rank-revealing factorizations, such as a partial QR factorization or a partial singular value decomposition. The method takes as input a tolerance epsilon and an mxn matrix A and returns an approximate low-rank factorization of A that is accurate to within precision epsilon in the Frobenius norm (or some other easily computed norm). The rank k of the computed factorization (which is an output of the algorithm) is in all examples we examined very close to the theoretically optimal epsilon-rank. The proposed method is inspired by the Gram-Schmidt algorithm and has the same O(mnk) asymptotic flop count. However, the method relies on randomized sampling to avoid column pivoting, which allows it to be blocked, and hence accelerates practical computations by reducing communication. Numerical experiments demonstrate that the accuracy of the scheme is for every matrix that was tried at least as good as column-pivoted QR and is sometimes much better. Computational speed is also improved substantially, in particular on GPU architectures.
暂无评论