An alternate proof of the algorithmic Lovász local lemma

Ioannis Giotis; Lefteris Kirousis; Kostas I. Psaromiligkos; Dimitrios M. Thilikos

doi:10.1007/978-3-319-51753-7_10

An alternate proof of the algorithmic Lovász local lemma

Ioannis Giotis, Lefteris Kirousis, Kostas I. Psaromiligkos, Dimitrios M. Thilikos

Computer Science

Research output: Contribution to journal › Article › peer-review

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.

Original language	English (US)
Pages (from-to)	61-65
Number of pages	5
Journal	Trends in Mathematics
Volume	6
DOIs	https://doi.org/10.1007/978-3-319-51753-7_10
State	Published - 2017

ASJC Scopus subject areas

General Mathematics

Access to Document

10.1007/978-3-319-51753-7_10

Cite this

@article{2109324291be47eaa0999816cd411987,

title = "An alternate proof of the algorithmic Lov{\'a}sz local lemma",

abstract = "The algorithm for Lov{\'a}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.",

author = "Ioannis Giotis and Lefteris Kirousis and Psaromiligkos, {Kostas I.} and Thilikos, {Dimitrios M.}",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.",

year = "2017",

doi = "10.1007/978-3-319-51753-7_10",

language = "English (US)",

volume = "6",

pages = "61--65",

journal = "Trends in Mathematics",

issn = "2297-0215",

publisher = "Springer International Publishing AG",

}

TY - JOUR

T1 - An alternate proof of the algorithmic Lovász local lemma

AU - Giotis, Ioannis

AU - Kirousis, Lefteris

AU - Psaromiligkos, Kostas I.

AU - Thilikos, Dimitrios M.

N1 - Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85014119333&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85014119333&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-51753-7_10

DO - 10.1007/978-3-319-51753-7_10

M3 - Article

AN - SCOPUS:85014119333

SN - 2297-0215

VL - 6

SP - 61

EP - 65

JO - Trends in Mathematics

JF - Trends in Mathematics

ER -

An alternate proof of the algorithmic Lovász local lemma

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this