Journal
SIAM JOURNAL ON DISCRETE MATHEMATICS
Volume 28, Issue 2, Pages 911-917Publisher
SIAM PUBLICATIONS
DOI: 10.1137/110828290
Keywords
local lemma; algorithm; partition function
Categories
Funding
- NSF MSPRF [1004696]
- Direct For Mathematical & Physical Scien
- Division Of Mathematical Sciences [1004696] Funding Source: National Science Foundation
Ask authors/readers for more resources
A recent theorem of Bissacot et al. [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 Bissacot et al. applicable in the Moser-Tardos algorithmic framework.
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