AN EXTENSION OF THE MOSER-TARDOS ALGORITHMIC LOCAL LEMMA

作者：Pegden Wesley^*

来源：SIAM Journal on Discrete Mathematics, 2014, 28(2): 911-917.

DOI：10.1137/110828290

• local lemma
• algorithm
• partition function

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.

• 出版日期2014