Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution

作者：Harris David G^*; Srinivasan Aravind

来源：ACM Transactions on Algorithms, 2017, 13(3): 33.

DOI：10.1145/3089869

• Lovasz Local Lemma
• Moser-Tardos algorithm
• LLL distribution
• MT distribution
• graph coloring
• satisfiability
• Latin transversals
• combinatorial enumeration

Moser and Tardos have developed a powerful algorithmic approach (henceforth MT) to the Lovasz Local Lemma (LLL); the basic operation done in MT and its variants is a search for "bad" events in a current configuration. In the initial stage of MT, the variables are set independently. We examine the distributions on these variables that arise during intermediate stages of MT. We show that these configurations have a more or less "random" form, building further on the MT-distribution concept of Haeupler et al. in understanding the (intermediate and) output distribution of MT. This has a variety of algorithmic applications; the most important is that bad events can be found relatively quickly, improving on MT across the complexity spectrum. It makes some polynomial-time algorithms sublinear (e.g., for Latin transversals, which are of basic combinatorial interest), gives lower-degree polynomial runtimes in some settings, transforms certain superpolynomial-time algorithms into polynomial-time algorithms, and leads to Las Vegas algorithms for some coloring problems for which only Monte Carlo algorithms were known.
We show that, in certain conditions when the LLL condition is violated, a variant of the MT algorithm can still produce a distribution that avoids most of the bad events. We show in sonic cases that this MT variant can run faster than the original MT algorithm itself and develop the first-known criterion for the case of the asymmetric LLL. This can be used to find partial Latin transversals-improving on earlier bounds of Stein (1975)-among other applications. We furthermore give applications in enumeration, showing that most applications (for which we aim for all or most of the bad events to be avoided) have large solution sets. We do this by showing that the MT distribution has large Renyi entropy.

• 出版日期2017-8