Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution

DOI10.1137/1.9781611974331.ch140zbMath1410.05221arXiv1507.02674MaRDI QIDQ4575725

Aravind Srinivasan, David G. Harris

Publication date: 16 July 2018

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

Full work available at URL: https://arxiv.org/abs/1507.02674

zbMATH Keywords

graph coloring; combinatorial enumeration; satisfiability; Lovász local lemma; Latin transversals; Moser-Tardos algorithm; LLL-distribution; MT-distribution; LLL distribution; MT distribution

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

60C05: Combinatorial probability

05C15: Coloring of graphs and hypergraphs

05D15: Transversal (matching) theory

05D40: Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)