Derandomizing the Lovasz Local Lemma more effectively
Derandomizing the Lovasz Local Lemma more effectively
复制标题
更有效地对 Lovasz 局部引理进行去随机化
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Robin A. Moser
中科院分区：
文献类型：
--
作者：
Robin A. Moser
著名的Lovasz局部引理[EL75]是一个强有力的工具，它可以非构造性地证明满足给定准则集合的组合对象的存在性。Kratochvil等人。应用这个技巧证明了每个变量最多出现2k/(Ek)次的k-CNF总是可满足的[KST93]。在一篇突破性的论文中，Beck发现，如果我们将出现次数降低到O(2^(k/48)/k)，那么确定性多项式时间算法可以找到对这样一个实例的满意分配[Bec91]。ALON将算法随机化，需要O(2^(k/8)/k)次[Alo91]。在[Mos06]中，我们展示了他的方法的一个改进，它可以处理其中的O(2^(k/6)/k)个。迄今为止最著名的随机化算法是由斯里尼瓦桑提出的，能够解决O(2^(k/4)/k)个出现实例[Sri08]。在回答斯里尼瓦桑提出的两个问题时，我们现在将提出一种方法，它允许每个变量出现O(2^(k/2)/k)次，并且最容易被去随机化。新算法基于另一种类型的见证树结构，并删除了所有以前方法共有的一些限制方面。
The famous Lovasz Local Lemma [EL75] is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. Kratochvil et al. applied this technique to prove that a k-CNF in which each variable appears at most 2^k/(ek) times is always satisfiable [KST93]. In a breakthrough paper, Beck found that if we lower the occurrences to O(2^(k/48)/k), then a deterministic polynomial-time algorithm can find a satisfying assignment to such an instance [Bec91]. Alon randomized the algorithm and required O(2^(k/8)/k) occurrences [Alo91]. In [Mos06], we exhibited a refinement of his method which copes with O(2^(k/6)/k) of them. The hitherto best known randomized algorithm is due to Srinivasan and is capable of solving O(2^(k/4)/k) occurrence instances [Sri08]. Answering two questions asked by Srinivasan, we shall now present an approach that tolerates O(2^(k/2)/k) occurrences per variable and which can most easily be derandomized. The new algorithm bases on an alternative type of witness tree structure and drops a number of limiting aspects common to all previous methods.