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).
作者：
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.
Inspired by the interesting idea of randomization, some powerful but time-consuming decomposition-ensemble learning paradigms can be extended into extremely efficient and fast variants by using randomized algorithms a...
详细信息
Inspired by the interesting idea of randomization, some powerful but time-consuming decomposition-ensemble learning paradigms can be extended into extremely efficient and fast variants by using randomized algorithms as individual forecasting tools. In the proposed methodology, Three major steps, (1) data decomposition via ensemble empirical mode decomposition, (2) individual prediction via a randomized algorithm (using randomization to mitigate training time and parameter sensitivity), and (3) results ensemble to produce final prediction, are included. Different from other existing decomposition-ensemble models using traditional econometric approaches or computational intelligence methods in individual prediction, this study employs some emerging randomized algorithms-extreme learning machine, random vector functional link network (using randomly fixed weights and bias in neural networks), and random kitchen sinks (using randomly mapping features to approximate kernels)-to dramatically save computational time and enhance prediction accuracy. With the Brent oil prices and the Henry Hub natural gas prices as studying samples, the empirical study statistically confirms that the proposed randomized-algorithm-based decomposition-ensemble learning models are proved to be excellently efficient and fast, relative to popular single techniques (including computational intelligence methods and randomized algorithms) and similar decomposition-ensemble counterparts (using the aforementioned single techniques as individual forecasting tools). (C) 2018 Elsevier Ltd. All rights reserved.
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.
A parallel randomized algorithm for finding the connected components of an undirected graph is presented. The algorithm has an expected running time of T = O(log(n)) with P = O((m + n)/log(n)) processors, where m is t...
详细信息
A parallel randomized algorithm for finding the connected components of an undirected graph is presented. The algorithm has an expected running time of T = O(log(n)) with P = O((m + n)/log(n)) processors, where m is the number of edges and n is the number of vertices. The algorithm is optimal in the sense that the product P . T is a linear function of the input size. The algorithm requires O(m + n) space, which is the input size, so it is optimal in space as well.
暂无评论