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.
The Moser-Tardos algorithm is known to terminate under criteria more general than , while still assuming the variable model. Pegden @cite_33 showed that the cluster expansion criterion suffices, whereas Kolipaka and Szegedy @cite_9 showed more generally that Shearer's criterion suffices. We also extend our analysis to the cluster expansion criterion as well as Shearer's criterion, in the more general context of . Our bounds on the number of resampling operations are somewhat weaker than those of @cite_33 @cite_9 , but the increase is at most quadratic.
@cite_9 @cite_33
2066969286 2075241889 2963097814 1810595280
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 The resampling algorithm of Moser & Tardos is a powerful approach to develop constructive versions of the Lovasz Local Lemma (LLL). We generalize this to partial resampling: when a bad event holds, we resample an appropriately-random subset of the variables that define this event, rather than the entire set as in Moser & Tardos. This is particularly useful when the bad events are determined by sums of random variables. This leads to several improved algorithmic applications in scheduling, graph transversals, packet routing etc. For instance, we improve the approximation ratio of a generalized @math -dimensional scheduling problem studied by Azar & Epstein from @math to @math , and settle a conjecture of Szabo & Tardos on graph transversals asymptotically. As a point of comparison with the MT algorithm, we show a family of constraint satisfaction problems that does not have "locality" (every constraint is affected by every variable), and so the LLL and the Moser-Tardos algorithm do not give any useful results; however, our method gives strong scale-free approximation ratios and terminates in expected polynomial time for this family. A recent theorem of [arXiv:0910.1824v2, 2010], proved using results about the cluster expansion in statistical mechanics, extends the Lovasz local lemma by weakening the conditions under which its conclusion holds. In this note, we prove an algorithmic analogue of this result, extending Moser and Tardos's recent algorithmic local lemma [J. ACM, 57 (2010), 11], and providing an alternative proof of the theorem of applicable in the Moser--Tardos algorithmic framework. The algorithm for Lovasz Local Lemma by Moser and Tardos gives a constructive way to prove the existence of combinatorial objects that satisfy a system of constraints. We present an alternative probabilistic analysis of the algorithm that does not involve reconstructing the history of the algorithm from the witness tree. We apply our technique to improve the best known upper bound to acyclic chromatic index. Specifically we show that a graph with maximum degree Δ has an acyclic proper edge coloring with at most ⌈3.74(Δ − 1)⌉ + 1 colors, whereas the previously known best bound was 4(Δ − 1). The same technique is also applied to improve corresponding bounds for graphs with bounded girth. An interesting aspect of this application is that the probability of the "undesirable" events do not have a uniform upper bound, i.e. it constitutes a case of the asymmetric Lovasz Local Lemma.