Journal
RANDOM STRUCTURES & ALGORITHMS
Volume 57, Issue 1, Pages 97-131Publisher
WILEY
DOI: 10.1002/rsa.20914
Keywords
Lovasz Local Lemma; Moser-Tardos algorithm; Boolean satisfiability; Independent transversals; Latin transversals
Funding
- NSF [CNS 1010789, CCF 1422569]
Ask authors/readers for more resources
The Lovasz local lemma (LLL) is a probabilistic tool to generate combinatorial structures with good local properties. The LLL-distribution further shows that these structures have good global properties in expectation. The seminal algorithm of Moser and Tardos turned the simplest, variable-based form of the LLL into an efficient algorithm; this has since been extended to other probability spaces including random permutations. One can similarly define an MT-distribution for these algorithms, that is, the distribution of the configuration they produce. We show new bounds on the MT-distribution in the variable and permutation settings which are significantly stronger than those known to hold for the LLL-distribution. As some example illustrations, we show a nearly tight bound on the minimum implicate size of a CNF Boolean formula, and we obtain improved bounds on weighted Latin transversals and partial Latin transversals.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available