research-article

Improved algorithmic versions of the Lovász Local Lemma

Author:

Aravind SrinivasanAuthors Info & Claims

SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 611 - 620

Published: 20 January 2008 Publication History

Abstract

The Lovász Local Lemma is a powerful tool in combinatorics and computer science. The original version of the lemma was nonconstructive, and efficient algorithmic versions have been developed by Beck, Alon, Molloy & Reed, et al. In particular, the work of Molloy & Reed lets us automatically extract efficient versions of essentially any application of the symmetric version of the Local Lemma. However, with some exceptions, there is a significant gap between what one can prove using the original Lemma nonconstructively, and what is possible through these efficient versions; also, some of these algorithmic versions run in super-polynomial time. Here, we lessen this gap, and improve the running time of all these applications (which cover all applications in the Molloy & Reed framework) to polynomial. We also improve upon the parallel algorithmic version of the Local Lemma for hypergraph coloring due to Alon, by allowing noticeably more overlap among the edges.

References

[1]

A. Ageev and M. Sviridenko, Pipage rounding: a new method of constructing algorithms with proven performance guarantee, Journal of Combinatorial Optimization, 8 (2004), pp. 307--328.

[2]

N. Alon, A parallel algorithmic version of the Local Lemma, Random Structures & Algorithms, 2 (1991), pp. 367--378.

[3]

N. Alon and J. H. Spencer, The Probabilistic Method, Second Edition, Wiley, 2000.

[4]

J. Beck, An algorithmic approach to the Lovász Local Lemma, Random Structures & Algorithms, 2 (1991), pp. 343--365.

[5]

J. Beck and S. Lodha, Efficient proper 2-coloring of almost disjoint hypergraphs, Proc. ACM-SIAM Symposium on Discrete Algorithms, pp. 598--605, 2002.

Digital Library

[6]

A. Chattopadhyay and B. Reed, Properly 2-colouring linear hypergraphs, Proc. RANDOM 2007, Lecture Notes in Computer Science 4627, pages 395--408, 2007.

Digital Library

[7]

A. Czumaj and C. Scheideler, Coloring non-uniform hypergraphs: A new algorithmic approach to the General Lovász Local Lemma, Random Structures & Algorithms, 17 (2000), pp. 213--237.

Digital Library

[8]

A. Czumaj and C. Scheideler, A new algorithmic approach to the General Lovász Local Lemma with applications to scheduling and satisfiability problems, In Proc. ACM Symposium on Theory of Computing, pages 38--47, 2000.

Digital Library

[9]

P. Erdős and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, In Infinite and Finite Sets, A. Hajnal et. al., eds., Colloq. Math. Soc. J. Bolyai 11, North Holland, Amsterdam, 1975, pp. 609--627.

[10]

U. Feige, M. M. Halldórsson, G. Kortsarz and A. Srinivasan, Approximating the Domatic Number, SIAM Journal on Computing, 32 (2002), pp. 172--195.

Digital Library

[11]

R. Gandhi, S. Khuller, S. Parthasarathy, and A. Srinivasan, Dependent Rounding and its Applications to Approximation Algorithms, Journal of the ACM, 53 (2006), pp. 324--360.

Digital Library

[12]

M. Molloy and B. Reed, Further algorithmic aspects of the Local Lemma, In Proc. ACM Symposium on Theory of Computing, pages 524--529, 1998.

Digital Library

[13]

M. Molloy and B. Reed, Graph Colouring and the Probabilistic Method, Springer, 2000.

[14]

S. Pemmaraju and A. Srinivasan, The Randomized Coloring Procedure with Symmetry-Breaking, submitted.

[15]

J. Radhakrishnan and A. Srinivasan, Improved Bounds and Algorithms for Hypergraph 2-Coloring, Random Structures & Algorithms, 16 (2000), pp. 4--32.

Digital Library

[16]

M. R. Salavatipour, A (1 + ∈)-approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lovász Local Lemma, Random Structures & Algorithms, 25 (2004), pp. 68--90.

Digital Library

[17]

A. Srinivasan, Distributions on level-sets with applications to approximation algorithms, In Proc. IEEE Symposium on Foundations of Computer Science, pages 588--597, 2001.

Digital Library

Cited By

Guo HJerrum MLiu J(2019)Uniform Sampling Through the Lovász Local LemmaJournal of the ACM10.1145/331013166:3(1-31)Online publication date: 12-Apr-2019
https://dl.acm.org/doi/10.1145/3310131
Brandt SMaus YUitto JRobinson PEllen F(2019)A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local LemmaProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331636(389-398)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3293611.3331636
Harvey NSrivastava PVondrák JCzumaj A(2018)Computing the independence polynomialProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175407(1557-1576)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175407
Show More Cited By

Index Terms

Improved algorithmic versions of the Lovász Local Lemma
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
    2. Graph theory
      1. Graph algorithms
  2. Mathematical analysis
    1. Numerical analysis
      1. Computations in finite fields
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Directed Lovász local lemma and Shearer’s lemma
Abstract
Moser and Tardos (J. ACM (JACM) 57(2), 11 2010) gave an algorithmic proof of the lopsided Lovász local lemma (LLL) in the variable framework, where each of the undesirable events is assumed to depend on a subset of a collection of independent ...
Deterministic algorithms for the Lovász Local Lemma
SODA '10: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms

The Lovász Local Lemma [5] (LLL) is a powerful result in probability theory that states that the probability that none of a set of bad events happens is nonzero if the probability of each event is small compared to the number of events that depend on ...
An algorithmic approach to the lovász local lemma. I

The Lovász Local Lemma is a remarkable sieve method to prove the existence of certain structures without supplying any efficient way of finding these structures. In this article we convert some of the applications of the Local Lemma into polynomial time ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms

January 2008

1289 pages

Program Chair:
Shang-Hua Teng
Boston University and Akamai Technologies, Inc.

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 20 January 2008

Check for updates

Qualifiers

Research-article

Conference

SODA08

Sponsor:

SIGACT

SODA08: 19th ACM-SIAM Symposium on Discrete Algorithms

January 20 - 22, 2008

California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
348
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Guo HJerrum MLiu J(2019)Uniform Sampling Through the Lovász Local LemmaJournal of the ACM10.1145/331013166:3(1-31)Online publication date: 12-Apr-2019
https://dl.acm.org/doi/10.1145/3310131
Brandt SMaus YUitto JRobinson PEllen F(2019)A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local LemmaProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331636(389-398)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3293611.3331636
Harvey NSrivastava PVondrák JCzumaj A(2018)Computing the independence polynomialProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175407(1557-1576)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175407
Guo HJerrum MLiu JHatami HMcKenzie PKing V(2017)Uniform sampling through the Lovasz local lemmaProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055410(342-355)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3055399.3055410
Brandt SFischer OHirvonen JKeller BLempiäinen TRybicki JSuomela JUitto JWichs DMansour Y(2016)A lower bound for the distributed Lovász local lemmaProceedings of the forty-eighth annual ACM symposium on Theory of Computing10.1145/2897518.2897570(479-488)Online publication date: 19-Jun-2016
https://dl.acm.org/doi/10.1145/2897518.2897570
Achlioptas DIliopoulos F(2016)Random Walks That Find Perfect Objects and the Lovász Local LemmaJournal of the ACM10.1145/281835263:3(1-29)Online publication date: 21-Jul-2016
https://dl.acm.org/doi/10.1145/2818352
Chung KPettie SSu HHalldórsson MDolev S(2014)Distributed algorithms for the Lovász local lemma and graph coloringProceedings of the 2014 ACM symposium on Principles of distributed computing10.1145/2611462.2611465(134-143)Online publication date: 15-Jul-2014
https://dl.acm.org/doi/10.1145/2611462.2611465
Ambainis AKempe JSattath O(2012)A quantum Lovász local lemmaJournal of the ACM10.1145/2371656.237165959:5(1-24)Online publication date: 5-Nov-2012
https://dl.acm.org/doi/10.1145/2371656.2371659
Messner JThierauf T(2012)A Kolmogorov complexity proof of the Lovász Local Lemma for satisfiabilityTheoretical Computer Science10.1016/j.tcs.2012.06.005461(55-64)Online publication date: 1-Nov-2012
https://dl.acm.org/doi/10.1016/j.tcs.2012.06.005
Messner JThierauf T(2011)A kolmogorov complexity proof of the lovász local lemma for satisfiabilityProceedings of the 17th annual international conference on Computing and combinatorics10.5555/2033094.2033109(168-179)Online publication date: 14-Aug-2011
https://dl.acm.org/doi/10.5555/2033094.2033109
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents