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.