Article

Free access

Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovász local lemma

Authors:

Artur Czumaj,

Christian ScheidelerAuthors Info & Claims

SODA '00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms

Pages 30 - 39

Published: 01 February 2000 Publication History

PDF eReader

References

[1]

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

Google Scholar

[2]

N. Alon, A. Bax-Noy, N. Linial, and D. Peleg. On the complexity of radio communication. In Proceedings of the 21st Annual A CM Symposium on Theory of Computing, pages 274-285, 1989.

Digital Library

Google Scholar

[3]

N. Alon, O. Goldreich, j. H~stad, and R. Peralta. Simple constructions of almost k-wise independent random variables. Random Structures and Algorithms, 3(3):289-304, 1992.

Google Scholar

[4]

N. Alon, C. McDiarmid, and B. Reed. Acyclic coloring of graphs. Random Structures and Algorithms, 2(3):277-288, 1991.

Google Scholar

[5]

N. Alon and J. H. Spencer. The Probabilistic Method. Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, New York, 1992.

Google Scholar

[6]

J. Beck. An algorithmic approach to the Lov~sz Local Lemma. I. Random Structures and Algorithms, 2(4):343-365, 1991.

Google Scholar

[7]

A. Z. Broder, A. M. Frieze, and E. Upfal. Static and dynamic path selection on expander graphs: A random walk approach. In Proceedings of the 29th Annual A CM Symposium on Theory of Computing, pages 531- 539, 1997.

Digital Library

Google Scholar

[8]

P. Erd6s and L. Lov~sz. Problems and results on 3- chromatic hypergraphs and some related questions. In A. Hajnal, R. Rado, and V. T. S6s, editors, Infinite and Finite Sets (to Paul ErdSs on his 60th birthday), volume II, pages 609-627. North-Holland, 1975.

Google Scholar

[9]

P. Erd6s and J. Spencer. Lopsided Lov~z local lemma and latin transversals. Discrete Applied Mathematics, 30:151-154, 1991.

Digital Library

Google Scholar

[10]

G. Even, O. Goldreich, M. Luby, N. Nisan, and B. Veli~kovi6. Efficient approximations of product distributions. Random Structures and Algorithms, 13(1):1-16, 1998.

Digital Library

Google Scholar

[11]

U. Feige and C. Scheideler. improved bounds for acyclic job shop scheduling. In Proceedings of the 30th Annual A CM Symposium on Theory of Computing, pages 624-633, 1998.

Digital Library

Google Scholar

[12]

H. Hind, M. Molloy, and B. Reed. Colouring a graph frugally. Combinatorica, 17(4):469-482, 1997.

Google Scholar

[13]

F. T. Leighton, B. M. Maggs, and S. B. Rao. Packet routing and job-shop scheduling in O(Congestion + Dilation) steps. Combinatorica, 14(2):167-180, 1994.

Google Scholar

[14]

F. T. Leighton, B. M. Maggs, and A. W. Richa. Fast algorithms for finding O(Congestion + Dilation) packet routing schedules. Combinatorica, 19(3):375- 401, 1999.

Google Scholar

[15]

T. Leighton, S. Rao, and A. Srinivasan. New algorithmic aspects of the Local Lemma with applications to routing and partitioning. In Proceedings of the l Oth Annual A CM-SIAM Symposium on Discrete Algorithms, pages 643-652, 1999.

Digital Library

Google Scholar

[16]

C.J. Lu. A deterministic approximation algorithm for a minmax integer programming problem. In Proceedings of the lOth Annual A CM-SIAM Symposium on Discrete Algorithms, pages 663-668, 1999.

Digital Library

Google Scholar

[17]

M. Molloy. The probabilistic method. In M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, editors, Probabilistic Methods for Algorithmic Discrete Mathematics, pages 1-35. Springer-Verlag, 1998.

Google Scholar

[18]

M. Molloy and B. Reed. Further algorithmic aspects of the Local Lemma. In Proceedings of the 30th Annual A CM Symposium on Theory of Computing, pages 524- 529, 1998.

Digital Library

Google Scholar

[19]

J. Naor and J. Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM Journal on Computing, 22(4):838-856, 1993.

Digital Library

Google Scholar

[20]

J. Radhakrishnan and A. Srinivasan. Improved bounds and algorithms for hypergraph two-coloring, in Proceedings of the 39th IEEE Symposium on Foundations of Computer Science, pages 684-693, 1998.

Digital Library

Google Scholar

[21]

B. Reed. w, A, and X. Journal of Graph Theory, 27(4):177-212, 1998.

Digital Library

Google Scholar

[22]

j. Spencer. Ten Lectures on the Probabilistic Method. 2nd Edition. SIAM, 1994.

Google Scholar

[23]

A. Srinivasan. An extension of the Lov~sz Local Lemma, and its applications to integer programming. In Proceedings of the 7th Annual A CM-SIAM Symposium on Discrete Algorithms, pages 6-15, 1996.

Digital Library

Google Scholar

Cited By

View all

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
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
Haeupler BSaha BSrinivasan A(2011)New Constructive Aspects of the Lovász Local LemmaJournal of the ACM10.1145/2049697.204970258:6(1-28)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1145/2049697.2049702
Show More Cited By

Index Terms

Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovász local lemma
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Hypergraphs
  2. Probability and statistics
2. Theory of computation
  1. Models of computation
    1. Probabilistic computation

Recommendations

Coloring Non-uniform Hypergraphs Without Short Cycles

The work deals with a generalization of Erd s---Lovász problem concerning colorings of non-uniform hypergraphs. Let H = ( V , E ) be a hypergraph and let $${{f_r(H)=\sum\limits_{e \in E}r^{1-|e|}}}$$ f r ( H ) = e E r 1 - | e | for some r 2. Erd s and Lovász proposed to find the value f ( n ) equal to the minimum ...
Covering Non-uniform Hypergraphs

A subset of the vertices in a hypergraph is a cover if it intersects every edge. Let (H) denote the cardinality of a minimum cover in the hypergraph H, and let us denote by g(n) the maximum of (H) taken over all hypergraphs H with n vertices and with no ...
Colouring Clique-Hypergraphs of Circulant Graphs

A clique-colouring of a graph G is a colouring of the vertices of G so that no maximal clique of size at least two is monochromatic. The clique-hypergraph, $${\mathcal{H}(G)}$$ , of a graph G has V ( G ) as its set of vertices and the maximal cliques of G as its ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms

February 2000

965 pages

ISBN:0898714532

Chairman:
David Shmoys

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 February 2000

Check for updates

Qualifiers

Article

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
276
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)9

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

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
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
Haeupler BSaha BSrinivasan A(2011)New Constructive Aspects of the Lovász Local LemmaJournal of the ACM10.1145/2049697.204970258:6(1-28)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1145/2049697.2049702
Kolipaka KSzegedy MFortnow LVadhan S(2011)Moser and tardos meet LovászProceedings of the forty-third annual ACM symposium on Theory of computing10.1145/1993636.1993669(235-244)Online publication date: 6-Jun-2011
https://dl.acm.org/doi/10.1145/1993636.1993669
Ambainis AKempe JSattath OMitzenmacher MSchulman L(2010)A quantum lovász local lemmaProceedings of the forty-second ACM symposium on Theory of computing10.1145/1806689.1806712(151-160)Online publication date: 5-Jun-2010
https://dl.acm.org/doi/10.1145/1806689.1806712
Moser RTardos G(2010)A constructive proof of the general lovász local lemmaJournal of the ACM10.1145/1667053.166706057:2(1-15)Online publication date: 8-Feb-2010
https://dl.acm.org/doi/10.1145/1667053.1667060
Moser RMitzenmacher M(2009)A constructive proof of the Lovász local lemmaProceedings of the forty-first annual ACM symposium on Theory of computing10.1145/1536414.1536462(343-350)Online publication date: 31-May-2009
https://dl.acm.org/doi/10.1145/1536414.1536462
Srivastav A(2005)The lovász-local-lemma and schedulingEfficient Approximation and Online Algorithms10.5555/2168139.2168151(321-347)Online publication date: 1-Jan-2005
https://dl.acm.org/doi/10.5555/2168139.2168151
Salavatipour M(2004)A (1 + ε)-approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lovász local LemmaRandom Structures & Algorithms10.1002/rsa.2001625:1(68-90)Online publication date: 1-Aug-2004
https://dl.acm.org/doi/10.1002/rsa.20016
Salavatipour M(2003)A (1 + ε)-approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lovász Local LemmaProceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/644108.644165(347-356)Online publication date: 12-Jan-2003
https://dl.acm.org/doi/10.5555/644108.644165
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

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

Cited By

Index Terms

Recommendations

Coloring Non-uniform Hypergraphs Without Short Cycles

Covering Non-uniform Hypergraphs

Colouring Clique-Hypergraphs of Circulant Graphs