An Algorithmic Approach to the Lovász Local Lemma. I
An Algorithmic Approach to the Lovász Local Lemma. I
复制标题
DOI：
10.1002/rsa.3240020402
复制
发表时间：
1991-12
期刊：
影响因子：
--
通讯作者：
J. Beck
中科院分区：
文献类型：
--
作者：
J. Beck
Lovasz局部引理是一种证明某些结构存在的显着的筛法，但没有提供任何有效的方法来找到这些结构。在这篇文章中，我们将局部引理的一些应用转换为多项式时间序列算法（以“指数”中较弱的常数因子为代价）。我们的主要例子如下：假设在一个n-均匀超图中，每个超边最多与2n/48个其他超边相交，那么有一个多项式时间算法，可以找到这些点的一个双染色，使得没有超边是单色的。© 1991 Wiley Periodicals，Inc.
The Lovasz Local Lemma is a remarkable sieve method to prove the existence of certain structures without supplying any efficient way of finding these structures. In this article we convert some of the applications of the Local Lemma into polynomial time sequential algorithms (at the cost of a weaker constant factor in the “exponent”). Our main example is the following: assume that in an n‐uniform hypergraph every hyperedge intersects at most 2n/48 other hyperedges, then there is a polynomial time algorithm that finds a two‐coloring of the points such that no hyperedge is monochromatic. © 1991 Wiley Periodicals, Inc.