Access Restriction

Author Haeupler, Bernhard ♦ Saha, Barna ♦ Srinivasan, Aravind
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2011
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Lovâsz Local Lemma (LLL) ♦ Monte Carlo algorithms ♦ Constructive ♦ Exponentially many bad events
Abstract The Lovász Local Lemma (LLL) is a powerful tool that gives sufficient conditions for avoiding all of a given set of “bad” events, with positive probability. A series of results have provided algorithms to efficiently construct structures whose existence is non-constructively guaranteed by the LLL, culminating in the recent breakthrough of Moser and Tardos [2010] for the full asymmetric LLL. We show that the output distribution of the Moser-Tardos algorithm well-approximates the conditional LLL-distribution, the distribution obtained by conditioning on all bad events being avoided. We show how a known bound on the probabilities of events in this distribution can be used for further probabilistic analysis and give new constructive and nonconstructive results. We also show that when a LLL application provides a small amount of slack, the number of resamplings of the Moser-Tardos algorithm is nearly linear in the number of underlying independent variables (not events!), and can thus be used to give efficient constructions in cases where the underlying proof applies the LLL to super-polynomially many events. Even in cases where finding a bad event that holds is computationally hard, we show that applying the algorithm to avoid a polynomial-sized “core” subset of bad events leads to a desired outcome with high probability. This is shown via a simple union bound over the probabilities of non-core events in the conditional LLL-distribution, and automatically leads to simple and efficient Monte-Carlo (and in most cases $\textit{RNC})$ algorithms. We demonstrate this idea on several applications. We give the first constant-factor approximation algorithm for the Santa Claus problem by making a LLL-based proof of Feige constructive. We provide Monte Carlo algorithms for acyclic edge coloring, nonrepetitive graph colorings, and Ramsey-type graphs. In all these applications, the algorithm falls directly out of the non-constructive LLL-based proof. Our algorithms are very simple, often provide better bounds than previous algorithms, and are in several cases the first efficient algorithms known. As a second type of application we show that the properties of the conditional LLL-distribution can be used in cases beyond the critical dependency threshold of the LLL: avoiding all bad events is impossible in these cases. As the first (even nonconstructive) result of this kind, we show that by sampling a selected smaller core from the LLL-distribution, we can avoid a fraction of bad events that is higher than the expectation. MAX $\textit{k}-SAT$ is an illustrative example of this.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2011-12-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 58
Issue Number 6
Page Count 28
Starting Page 1
Ending Page 28

Open content in new tab

   Open content in new tab
Source: ACM Digital Library