Loading...
Please wait, while we are loading the content...
Similar Documents
A parallel algorithmic version of the local lemma.
| Content Provider | CiteSeerX |
|---|---|
| Author | Alon, Noga |
| Abstract | The Lovász Local Lemma is a tool that enables one to show that certain events hold with positive, though very small probability. It often yields existence proofs of results without supplying any efficient way of solving the corresponding algorithmic problems. J. Beck has recently found a method for converting some of these existence proofs into efficient algorithmic procedures, at the cost of loosing a little in the estimates. His method does not seem to be parallelizable. Here we modify his technique in several points and achieve an algorithmic version that can be parallelized, thus obtaining deterministic NC¹ algorithms for various interesting algorithmic search problems. Two representing examples are the problem of finding a directed even simple cycle in a digraph in which the maximum outdegree is at most a small exponent of the minimum indegree and the problem of exhibiting a satisfying assignment for a Boolean CNF Formula in which the maximum number of occurences of each literal is bounded by a small exponent of the minimum number of literals in a disjunction. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Efficient Algorithmic Procedure Deterministic Nc Algorithm Corresponding Algorithmic Problem Small Probability Algorithmic Version Certain Event Satisfying Assignment Simple Cycle Existence Proof Boolean Cnf Formula Maximum Outdegree Minimum Indegree Local Lemma Several Point Parallel Algorithmic Version Maximum Number Efficient Way Small Exponent Various Interesting Algorithmic Search Problem Minimum Number |
| Content Type | Text |
