By using projections by a block of vectors in place of a single vector it is possible to parallelize the outer loop of iterative methods for solving sparse linear systems. We analyze such a scheme proposed by Coppersm...
详细信息
By using projections by a block of vectors in place of a single vector it is possible to parallelize the outer loop of iterative methods for solving sparse linear systems. We analyze such a scheme proposed by Coppersmith for Wiedemann's coordinate recurrence algorithm, which is based in part on the Krylov subspace approach. We prove that by use of certain randomizations on the input system the parallel speed up is roughly by the number of vectors in the blocks when using as many processors. Our analysis is valid for fields of entries that have sufficiently large cardinality. Our analysis also deals with an arising subproblem of solving a singular block Toeplitz system by use of the theory of Toeplitz-like matrices.
randomized algorithms for two sorting problems are presented. In the local sorting problem, a graph is given in which each vertex is assigned an element of a total order, and the task is to determine the relative orde...
详细信息
randomized algorithms for two sorting problems are presented. In the local sorting problem, a graph is given in which each vertex is assigned an element of a total order, and the task is to determine the relative order of every pair of adjacent vertices. In the set-maxima problem, a collection of sets whose elements are drawn from a total order is given, and the task is to determine the maximum element in each set. Lower bounds for the problems in the comparison model are described and it is shown that the algorithms are optimal within a constant factor.
We present randomized approximation algorithms for the maximum cut (MAX CUT) and maximum 2-satisfiability (MAX 2SAT) problems that always deliver solutions of expected value at least .87856 times the optimal value. Th...
详细信息
We present randomized approximation algorithms for the maximum cut (MAX CUT) and maximum 2-satisfiability (MAX 2SAT) problems that always deliver solutions of expected value at least .87856 times the optimal value. These algorithms use a simple and elegant technique that randomly rounds the solution to a nonlinear programming relaxation. This relaxation can be interpreted both as a semidefinite program and as an eigenvalue minimization problem. The best previously known approximation algorithms for these problems had performance guarantees of 1/2 for MAX CUT and 3/4 for MAX 2SAT. Slight extensions of our analysis lead to a .79607-approximation algorithm for the maximum directed cut problem (MAX DICUT) and a .758-approximation algorithm for MAX SAT, where the best previously known approximation algorithms had performance guarantees of 1/4 and 3/4, respectively. Our algorithm gives the first substantial progress in approximating MAX CUT in nearly twenty years, and represents the first use of semidefinite programming in the design of approximation algorithms.
We introduce new, elementary Monte Carlo methods to speed up and greatly simplify the manipulation of permutation groups (given by a list of generators). The methods are of a combinatorial character, using only elemen...
详细信息
We introduce new, elementary Monte Carlo methods to speed up and greatly simplify the manipulation of permutation groups (given by a list of generators). The methods are of a combinatorial character, using only elementary group theory. The key idea is that under certain conditions, ''random subproducts'' of the generators successfully emulate truly random elements of a group. We achieve a nearly optimal O(n(3) log(c) n) asymptotic running time for membership testing, where n is the size of the permutation domain. This is an improvement of two orders of magnitude compared to known elementary algorithms and one order of magnitude compared to algorithms which depend on heavy use of group theory. An even greater asymptotic speedup is achieved for normal closures, a key ingredient in group-theoretic computation, now constructible in Monte Carlo time O(n(2) log(c) n), i.e., essentially linear time (as a function of the input length). Some of the new techniques are sufficiently general to allow polynomial-time implementations in the very general model of ''black box groups'' (group operations are performed by an oracle). In particular, the normal closure algorithm has a number of applications to matrix-group computation. It should be stressed that our randomized algorithms are not heuristic: the probability of error is guaranteed not to exceed a bound epsilon > 0, prescribed by the user, The cost of this requirement is a factor of \log epsilon\ in the running time. (C) 1995 Academic Press, Inc.
Hierarchical terrain models describe a topographic surface at different levels of detail, thus providing a multiresolution surface representation as well as a data compression mechanism. We consider the horizon comput...
详细信息
Hierarchical terrain models describe a topographic surface at different levels of detail, thus providing a multiresolution surface representation as well as a data compression mechanism. We consider the horizon computation problem on a hierarchical polyhedral terrain (in particular, on a hierarchical triangulated irregular network), which involves extracting the horizon of a viewpoint at a given resolution and updating it as the resolution increases. We present an overview of horizon computation algorithms on a nonhierarchical polyhedral terrain. We extend such algorithms to the hierarchical case by describing a method which extracts the terrain edges at a given resolution, and proposing a randomized algorithm for dynamically updating a horizon under insertions and deletions of terrain edges
作者：
RAMESH, HNYU
Courant Inst New York NY 10003 USA
The following bounds on the competitive ratios of deterministic and randomized on-line algorithms for traversing width-w layered graphs are obtained. 1. A deterministic algorithm with a competitive ratio of O(w(3)2(w)...
详细信息
The following bounds on the competitive ratios of deterministic and randomized on-line algorithms for traversing width-w layered graphs are obtained. 1. A deterministic algorithm with a competitive ratio of O(w(3)2(w)). This ratio is close to the lower bound of Ohm(2(w)) and improves upon the previous best upper bound of O(9(w)). 2. The first known polynomially competitive randomized algorithm with a competitive ratio of O(w(13)). This settles a conjecture due to Fiat et al. (A. Fiat, D. P. Foster, H. Karloff, V. Rabani, Y. Ravid, and S. Vishwanathan, in ''Proceedings 32nd Annual Symposium on Foundations of Computer Science, Sept. 1991). 3. A lower bound of Ohm(w(2))/(log(1+epsilon)w)) on the competitive ratio of any randomized algorithm for this problem, where epsilon is any positive number. The previous best lower bound was linear. (C) 1995 Academic Press, Inc.
The existence of a random coin has been extensively assumed for applications such as randomizing algorithms, cryptographic protocols, and stochastic simulation experiments. The available sources of randomness are som...
详细信息
The existence of a random coin has been extensively assumed for applications such as randomizing algorithms, cryptographic protocols, and stochastic simulation experiments. The available sources of randomness are sometimes physical devices, such as Zener diodes and Geiger counters. The sample mean of the devices as an estimate of the bias of a random coin is always rational. A probabilistic Turing machine (PTM) is a Turing machine with distinguished states called coin-tossing states. The interchangeability of the simulation among coins is measured only by the expected time of computation. However, it is necessary to terminate in bounded time on some applications such as real-time operations and synchronous machines. In the present analysis, the computation which will always terminate in bounded time, as opposed to expected time, is considered. It is shown that the conceptual difference breaks the interchangeability of the coins. It is said that a PTM efficiently computes when it always terminates in bounded time.
randomized algorithms are analyzed as if unlimited amounts of perfect randomness were available, while pseudorandom number generation is usually studied from the perspective of cryptographic security or for the statis...
详细信息
randomized algorithms are analyzed as if unlimited amounts of perfect randomness were available, while pseudorandom number generation is usually studied from the perspective of cryptographic security or for the statistical properties of the numbers generated. Bach proposed studying the interaction between pseudorandom number generators and randomized algorithms. This paper follows Bach's lead;the authors assume that a (small) random seed is available to start up a simple pseudorandom number generator that is then used for the randomized algorithm. randomized algorithms are studied for (1) sorting, (2) selection, and (3) oblivious routing in networks.
The purpose of this paper is a study of computation that can be done locally in a distributed network, where ''locally'' means within time (or distance) independent of the size of the network. Locally ...
详细信息
The purpose of this paper is a study of computation that can be done locally in a distributed network, where ''locally'' means within time (or distance) independent of the size of the network. Locally checkable labeling (LCL) problems are considered, where the legality of a labeling can be checked locally (e.g., coloring). The results include the following: There are nontrivial LCL problems that have local algorithms. There is a variant of the dining philosophers problem that can be solved locally. Randomization cannot make an LCL problem local;i.e., if a problem has a local randomized algorithm then it has a local deterministic algorithm. It is undecidable, in general, whether a given LCL has a local algorithm. However, it is decidable whether a given LCL has an algorithm that operates in a given lime t. Any LCL problem that has a local algorithm has one that is order-invariant (the algorithm depends only on the order of the processor IDs).
Chernoff-Hoeffding (CH) bounds are fundamental tools used in bounding the tail probabilities of the sums of bounded and independent random variables (r.v.'s). We present a simple technique that gives slightly bett...
详细信息
Chernoff-Hoeffding (CH) bounds are fundamental tools used in bounding the tail probabilities of the sums of bounded and independent random variables (r.v.'s). We present a simple technique that gives slightly better bounds than these and that more importantly requires only limited independence among the random variables, thereby importing a variety of standard results to the case of limited independence for free. Additional methods are also presented, and the aggregate results are sharp and provide a better understanding of the proof techniques behind these bounds. These results also yield improved bounds for various tail probability distributions and enable improved approximation algorithms for jobshop scheduling. The limited independence result implies that a reduced amount and weaker sources of randomness are sufficient for randomized algorithms whose analyses use the CH bounds, e.g., the analysis of randomized algorithms for random sampling and oblivious packet routing.
暂无评论