The Lovasz Local Lemma is a seminal result in probabilistic combinatorics. It gives a sufficient condition on a probability space and a collection of events for the existence of an outcome that simultaneously avoids all of those events. Finding such an outcome by an efficient algorithm has been an active research topic for decades. Breakthrough work of Moser and Tardos (2009) presented an efficient algorithm for a general setting primarily characterized by a product structure on the probability space. In this work we present an efficient algorithm for a much more general setting. Our main assumption is that there exist certain functions, called resampling oracles, that can be invoked to address the undesired occurrence of the events. We show that, in all scenarios to which the original Lovasz Local Lemma applies, there exist resampling oracles, although they are not necessarily efficient. Nevertheless, for essentially all known applications of the Lovasz Local Lemma and its generalizations, we have designed efficient resampling oracles. As applications of these techniques, we present new results for packings of Latin transversals, rainbow matchings and rainbow spanning trees.
Kolipaka and Szegedy @cite_9 present another algorithm, called GeneralizedResample, whose analysis proves the LLL under Shearer's condition for arbitrary probability spaces. GeneralizedResample is similar to in that they both work with abstract distributions and that they repeatedly choose a maximal independent set @math of undesired events to resample. However, the way that the bad events are resampled is different: GeneralizedResample needs to sample from @math , which is a complicated operation that seems difficult to implement efficiently. Thus can be viewed as a variant of GeneralizedResample that can be made efficient in all known scenarios.
@cite_9
2066969286
Beck's early work [3] gave an efficient version of the Lovasz Local Lemma(LLL) with significant compromise in the parameters. Following several improvements [1,7,4,13], Moser [8], and Moser and Tardos [9] obtained asymptotically optimal results in terms of the maximal degree. For a fixed dependency graph G the exact criterion under which LLL applies is given by Shearer in [12]. For a dependency structure G, let LO(G) be the set of those probability assignments to the nodes of G for which the Lovasz Local Lemma holds. We show that: Both the sequential and parallel ersions of the Moser-Tardos algorithm are efficient up to the Shearer's bound, by giving a tighter analysis. We also prove that, whenever p ∈ LO(G) (1+e), the expected running times of the sequential and parallel versions are at most n e and O(1 e log n e), the later when e