License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2012.16
URN: urn:nbn:de:0030-drops-38440
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3844/
Go to the corresponding LIPIcs Volume Portal

Achlioptas, Dimitris ; Gouleakis, Themis

Algorithmic Improvements of the Lovász Local Lemma via Cluster Expansion

pdf-format:
4.pdf (0.4 MB)

Abstract

The Lovasz Local Lemma (LLL) is a powerful tool that can be used to prove that an object having none of a set of bad properties exists, using the probabilistic method. In many applications of the LLL it is also desirable to explicitly construct the combinatorial object. Recently it was shown that this is possible using a randomized algorithm in the full asymmetric LLL setting [R. Moser and G. Tardos, 2010]. A strengthening of the LLL for the case of dense local neighborhoods proved in [R. Bissacot et al., 2010] was recently also made constructive in [W. Pegden, 2011]. In another recent work [B. Haupler, B. Saha, A. Srinivasan, 2010], it was proved that the algorithm of Moser and Tardos is still efficient even when the number of events is exponential. Here we prove that these last two contributions can be combined to yield a new version of the LLL.

BibTeX - Entry

@InProceedings{achlioptas_et_al:LIPIcs:2012:3844,
  author =	{Dimitris Achlioptas and Themis Gouleakis},
  title =	{{Algorithmic Improvements of the Lov{\'a}sz Local Lemma via Cluster Expansion }},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) },
  pages =	{16--23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2012/3844},
  URN =		{urn:nbn:de:0030-drops-38440},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.16},
  annote =	{Keywords: Probabilistic Method, Lov{\'a}sz Local Lemma, Algorithms}
}

Keywords: Probabilistic Method, Lovász Local Lemma, Algorithms
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Issue Date: 2012
Date of publication: 14.12.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI