An algorithmic approach to the Lovász local lemma. I 论文

摘要

Abstract The Lovász 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 2 n/48 other hyperedges, then there is a polynomial time algorithm that finds a two‐coloring of the points such that no hyperedge is monochromatic.