Theory of Computing
-------------------
Title     : A Constructive Lovász Local Lemma for Permutations
Authors   : David G. Harris and Aravind Srinivasan
Volume    : 13
Number    : 17
Pages     : 1-41
URL       : https://theoryofcomputing.org/articles/v013a017

Abstract
--------

While there has been significant progress on algorithmic aspects of
the Lovasz 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 \times n$ matrix in which each entry
appears at most $(27/256)n$ times, has a Latin transversal. We present
the first polynomial-time algorithm to construct such a transversal.
We also develop  RNC  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.


An extended abstract of this paper has appeared in the Proceedings of 
the 25th ACM-SIAM Symposium on Discrete Algorithms, 2014.