摘要：While there has been significant progress on algorithmic aspects of the Lovász Local Lemma (LLL) in recent years, a noteworthy exception is when the LLL is used in the context of random permutations. The breakthrough algorithm of Moser & Tardos only works in the setting of independent variables, and does not apply in this context. We resolve this by developing a randomized polynomial-time algorithm for such applications. A noteworthy application is for Latin transversals: the best general result known here (Bissacot et al., improving on Erdős and Spencer), states that any n×nn×n matrix in which each entry appears at most (27/256)n(27/256)n times, has a Latin transversal. We present the first polynomial-time algorithm to construct such a transversal. We also develop RNCRNC algorithms for Latin transversals, rainbow Hamiltonian cycles, strong chromatic number, and hypergraph packing.In addition to efficiently finding a configuration which avoids bad events, the algorithm of Moser & Tardos has many powerful extensions and properties. These include a well-characterized distribution on the output distribution, parallel algorithms, and a partial resampling variant. We show that our algorithm has nearly all of the same useful properties as the Moser--Tardos algorithm, and present a comparison of this aspect with recent work on the LLL in general probability spaces.
关键词：Lovász Local Lemma; Lopsided Lovász Local Lemma; random permutations; Moser-Tardos algorithm; Latin transversals; rainbow Hamiltonian cycles; strong chromatic number; hypergraph packing
