A Constructive Proof of the General Lovasz Local Lemma
A Constructive Proof of the General Lovasz Local Lemma
复制标题
DOI：
10.1145/1667053.1667060
复制
发表时间：
2010-01-01
影响因子：
2.5
通讯作者：
Tardos, Gabor
中科院分区：
文献类型：
--
作者：
Moser, Robin A.;Tardos, Gabor
Lovasz局部引理是Erdos和Lovasz于1975年发现的一个强有力的工具，它可以非构造性地证明满足一组给定条件的组合对象的存在性。1991年，约瑟夫·贝克（Jozsef Beck）第一个证明了在某些更严格的条件下可以给出一个构造性的变体，开始了一系列旨在改善其算法性能并放松其限制的研究。在这篇文章中，我们改进了最近的研究结果，以便提供一种方法，使几乎所有已知的应用程序的一般局部引理算法。
The Lovasz Local Lemma discovered by Erdos and Lovasz in 1975 is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. In 1991, Jozsef Beck was the first to demonstrate that a constructive variant can be given under certain more restrictive conditions, starting a whole line of research aimed at improving his algorithm's performance and relaxing its restrictions. In the present article, we improve upon recent findings so as to provide a method for making almost all known applications of the general Local Lemma algorithmic.