An Alternate Proof of the Algorithmic Lovász Local Lemma

Abstract : The algorithm for Lovász Local Lemma by Moser and Tardos gives a constructive way to prove the existence of combinatorial objects satisfying a system of constraints. We present an alternative probabilistic analysis of the algorithm that does not involve reconstructing the history of the algorithm. We apply our technique to improve the best known upper bound to acyclic chromatic index.
Document type :
Book sections
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01692634
Contributor : Isabelle Gouat <>
Submitted on : Thursday, January 25, 2018 - 12:26:14 PM
Last modification on : Tuesday, January 14, 2020 - 1:36:09 PM

Identifiers

Collections

Citation

Ioannis Giotis, Lefteris Kirousis, Kostas I. Psaromiligkos, Dimitrios M. Thilikos. An Alternate Proof of the Algorithmic Lovász Local Lemma. Extended Abstracts Summer 2015, 6, pp.61-65, 2017, Trends in Mathematics, 978-3-319-51752-0. ⟨10.1007/978-3-319-51753-7_10⟩. ⟨lirmm-01692634⟩

Share

Metrics

Record views

387