Deterministic algorithms for the Lovász Local Lemma
Deterministic algorithms for the Lovász Local Lemma
复制标题
Lovasz 局部引理的确定性算法
DOI：
10.1137/100799642
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Bernhard Haeupler
中科院分区：
文献类型：
--
作者：
Karthekeyan Chandrasekaran;Navin Goyal;Bernhard Haeupler
Lovász局部引理[5]（LLL）是概率论中的一个强大结果，它指出，如果每个事件的概率与依赖于它的事件数量相比较小，则一组不良事件中没有发生的概率是非零的。它通常与概率方法结合使用，用于非构造性存在证明。一个突出的应用是<i>k</i>-CNF公式，其中ll意味着，如果公式中的每个子句最多与<i>d</i>≤<i>2<sup>k</sup> / e</i>其他子句共享变量，则该公式具有令人满意的赋值。最近，Moser[13]给出了一种有效构造满意分配的随机化算法。随后，Moser和Tardos[14]给出了一种随机算法，在非常一般的算法框架中构造由LLL保证的结构。我们解决了Moser和Tardos对这些算法进行有效非随机化的主要问题。具体来说，对于一个<i>k</i>-CNF公式，具有<i>m</i>子句和<i>d</i>≤<i>2<sup>k/(1+ε)</sup> / e</i>，对于某些ε(0,1)，我们给出了一个在<i>Õ（m</i><sup>2(1+1ε)</sup>）时间内找到满意赋值的算法。这改进了Moser和Moser- tardos的确定性算法，其运行时间<i>m</i>Ω（<i>k</i><sup>2</sup>）和<i>m</i>Ω（<i>k</i>·1/ε）是<i>k</i> = Ω(1)的超多项式，以及其他先前的算法，这些算法仅适用于<i>d</i>≤2<sup><i>k</i>/16</sup> / <i>e</i>。我们的算法在Moser和Tardos[14]算法框架下有效地工作于非对称版本的LLL，并且还可以并行化，即使用多项式多个处理器具有多对数运行时间。
The Lovász Local Lemma [5] (LLL) is a powerful result in probability theory that states that the probability that none of a set of bad events happens is nonzero if the probability of each event is small compared to the number of events that depend on it. It is often used in combination with the probabilistic method for non-constructive existence proofs. A prominent application is to <i>k</i>-CNF formulas, where LLL implies that, if every clause in the formula shares variables with at most <i>d</i> ≤ <i>2<sup>k</sup> / e</i> other clauses then such a formula has a satisfying assignment. Recently, a randomized algorithm to efficiently construct a satisfying assignment was given by Moser [13]. Subsequently Moser and Tardos [14] gave a randomized algorithm to construct the structures guaranteed by the LLL in a very general algorithmic framework. We address the main problem left open by Moser and Tardos of derandomizing these algorithms efficiently. Specifically, for a <i>k</i>-CNF formula with <i>m</i> clauses and <i>d</i> ≤ <i>2<sup>k/(1+ε)</sup> / e</i> for some ε ε (0, 1), we give an algorithm that finds a satisfying assignment in time <i>Õ(m</i><sup>2(1+1ε)</sup>). This improves upon the deterministic algorithms of Moser and of Moser-Tardos with running times <i>m</i>Ω(<i>k</i><sup>2</sup>) and <i>m</i>Ω(<i>k</i>·1/ε) which are superpolynomial for <i>k</i> = ϖ(1) and upon other previous algorithms which work only for <i>d</i> ≤ 2<sup><i>k</i>/16</sup> / <i>e</i>. Our algorithm works efficiently for the asymmetric version of LLL under the algorithmic framework of Moser and Tardos [14] and is also parallelizable, i.e., has polylogarithmic running time using polynomially many processors.