An Alternate Proof of the Algorithmic Lovász Local Lemma - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Book Sections Year : 2017

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.
No file

Dates and versions

lirmm-01692634 , version 1 (25-01-2018)

Identifiers

Cite

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⟩
235 View
0 Download

Altmetric

Share

More