A constructive algorithm for the Lovász Local Lemma on permutations

DOI10.1137/1.9781611973402.68zbMath1423.05191OpenAlexW4231075269MaRDI QIDQ5384029

David G. Harris, Aravind Srinivasan

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973402.68

zbMATH Keywords

independent set polynomialLovasz local lemmaLatin transversal matrices

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial probability (60C05) Transversal (matching) theory (05D15) Randomized algorithms (68W20) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (10)

Commutativity in the Algorithmic Lovász Local Lemma ⋮ Rainbow Hamilton cycles and lopsidependency ⋮ Bounded colorings of multipartite graphs and hypergraphs ⋮ Unnamed Item ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles ⋮ Directed Lovász local lemma and Shearer's lemma ⋮ Distributed algorithms for the Lovász local lemma and graph coloring ⋮ Finding independent transversals efficiently ⋮ A Local Lemma for Focused Stochastic Algorithms

This page was built for publication: A constructive algorithm for the Lovász Local Lemma on permutations