Article

Free access

New algorithmic aspects of the Local Lemma with applications to routing and partitioning

Authors:

Tom Leighton,

Satish Rao,

Aravind SrinivasanAuthors Info & Claims

SODA '99: Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms

Pages 643 - 652

Published: 01 January 1999 Publication History

PDF eReader

References

[1]

N. Alon, Eigeavalues and e.zpanders, Combinatorica, 6 (1986), pp. 83-96.]]

Digital Library

Google Scholar

[2]

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

Google Scholar

[3]

N. Alon and F. R. K. Chung, Ezplicit construction of linear sized tolerant networks, Discrete Mathematics, 72 (1989), pp. 15-19.]]

Digital Library

Google Scholar

[4]

N. Alon and J. H. Spencer, The.Probabilistic Method, Wiley-Intexscience Series, John Wiley & Sons, Inc., New York, 1992.]]

Google Scholar

[5]

S. Arora, F. T. Leighton, and B. M. Maggs, On-line algorithms for path selection in a nonbloeking network, SIAM J. Comput., 25 (1996), pp. 600-625.]]

Digital Library

Google Scholar

[6]

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

Google Scholar

[7]

A. Broder, A. Frieze, S. Suen and E. Upfal, Optimal construction of edge-disjoint paths in random graphs, In Proc. ACM-SIAM Symposium on Discrete Algorithms, pages 603-612, 1994.]]

Digital Library

Google Scholar

[8]

A. Broder, A. Frieze, S. Suen and E. Upfal, An e#eient algorithm for the vertex-disjoint paths problem in random 9raphs, In Proc. ACM-SIAM Symposium on Discrete Algorithms, pages 261-268, 1996.]]

Digital Library

Google Scholar

[9]

A. Broder, A. Frieze and E. Upfal, Ex/stence and construction of edge-disjoint paths on expander graphs, SIAM J. Comput., 23 (1994), pp. 976-989.]]

Digital Library

Google Scholar

[10]

A. Broder, A. Frieze and E. Upfal, Static and dynamic path selection on e#ander graphs: a random walk approach, In Proc. ACM Symposium on the Theory of Computing, pages 531-539, 1997.]]

Digital Library

Google Scholar

[11]

A. Broder, A. Frieze and E. LTpfal, Full version of {10}. (Personal communication from A. Frieze, June 1998.)]]

Google Scholar

[12]

P. Erd6s 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. 3. Bolyai 11, North Holland, Amsterdam, 1975, pp. 609-627.]]

Google Scholar

[13]

A. Frieze, Disjoint paths in expander graphs via random walks: a short survey, In Proc. Workshop on Randomization and Approximation Techniques in Computer Science, 1998.]]

Digital Library

Google Scholar

[14]

A. Frieze and L. Zhao, Optimal construction of edgedisjoint paths in random regular graphs, In Proc. ACM- SIAM Symposium on Discrete Algorithms, 1999.]]

Digital Library

Google Scholar

[15]

Z. Fiiredi and J. Kahn, On the dimensions of ordered sets of bounded degree, Order, 3 (1986), pp. 15-20.]]

Google Scholar

[16]

J. Kleinberg, Approximation algorithms for disjoint paths problems, PhD Thesis, Department of EECS, MIT, 1996.]]

Digital Library

Google Scholar

[17]

J. Kleinberg and R. Rubinfeld, Short paths in expander graphs, In Proc. IEEE Symposium on Foundations of Computer Science, pages 86-95, 1996.]]

Digital Library

Google Scholar

[18]

J. Kleinberg and I#. Tardos, Disjoint paths in densely embedded networks, In Proc. IEEE Symposium on Foundations of Computer Science, pages 52-61, 1995.]]

Digital Library

Google Scholar

[19]

F. T. Leighton and S. B. Rao, An approximate maxflow rain-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms, In Proc. IEEE Symposium on Foundations of Computer Science, pages 422-431, 1988.]]

Google Scholar

[20]

F. T. Leighton and S. B. Rao, Circuit switching: a multi.commodity flow based approach, in Proc. Workshop on Randomized Parallel Computing, 1996.]]

Google Scholar

[21]

F. T. Leighton, S. B. Rao, and A. Srinivasan, Multicommodity flow and circuit switching, }n Proc. Hawaii International Conference on System Sciences, 1998.]]

Digital Library

Google Scholar

[22]

M. Lomonosov, Combinatorial approaches to multiflow problems, Discrete Applied Math., 11 (1985), pp. 1-94.]]

Google Scholar

[23]

C.-J. Lu, A deterministic approximation algorithm for a minmax integer programmin9 problem, In Proc. ACM-SIAM Symposium on Discrete Algorithms, 1999.]]

Digital Library

Google Scholar

[24]

A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica, $ (1988), pp. 261-277.]]

Google Scholar

[25]

M. Middendorf and F. Pfeiffer, On the complexity of the disjoint paths problem, Combinatorica, 13 (1993), pp. 97-107.]]

Google Scholar

[26]

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

Google Scholar

[27]

R. Motwani and P. tLaghavan, Randomized Algorithms, Cambridge University Press, 1995.]]

Digital Library

Google Scholar

[28]

D. Peleg and E. Upfal, Disjoint paths on expander graphs, Combinatorica, 9 (1989), pp. 289-313.]]

Google Scholar

[29]

P. Ragh#van and C. D. Thompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, 7 (1987), pp. 365-374.]]

Digital Library

Google Scholar

[30]

J. P. Schmidt, A. Siegel, and A. Srinivasan, Chernoff- Hoeffding bounds for applications with limited independence, SIAM Journal on Discrete Mathematics, 8 (1995), pp. 223-250.]]

Digital Library

Google Scholar

[31]

A. Schrijver, Homotopic routing methods, In Paths, Flows, and VLSI-Layout, B. Korte, L. Lov#sz, H. J. Pr5mel, and A. Schrijver, Editors, pages 329-371, Springer-Verlag, Berlin, 1990.]]

Google Scholar

[32]

P. D. Seymour, On odd cuts and planar multicommodityflows, J. London Math. Soc., 42 (1981), pp. 178-192.]]

Google Scholar

[33]

J. H. Spencer, Ten Lectures on the Probabilistic Method, SIAM, Philadelphia, 1987. (Second edition published in 1994.)]]

Google Scholar

[34]

J. H. Spencer, The probabilistic lens: Sperner, Turdn and Br@man revisited, In A Tribute to Paul Erdgs, A. Baker, B. Bollob#s, A. Hajnal, editors, Cambridge University Press, pages 391-396, 1990.]]

Google Scholar

[35]

A. Srinivasan, An extension of the Lovdsz Local Lemma, and its applications to integer programming, In Proc. ACM-SIAM Symposium on Discrete Algorithms, pages 6-15, 1996.]]

Digital Library

Google Scholar

[36]

E. Upfal, An O(IogN) deterministic packet routing scheme, in Proc. ACM Symposium on the Theory of Computing, pages 241-250, 1989.]]

Digital Library

Google Scholar

Cited By

View all

Vöcking BVitter JSpirakis PYannakakis M(2001)Almost optimal permutation routing on hypercubesProceedings of the thirty-third annual ACM symposium on Theory of computing10.1145/380752.380848(530-539)Online publication date: 6-Jul-2001
https://dl.acm.org/doi/10.1145/380752.380848
Czumaj AScheideler CShmoys D(2000)Coloring non-uniform hypergraphsProceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms10.5555/338219.338229(30-39)Online publication date: 1-Feb-2000
https://dl.acm.org/doi/10.5555/338219.338229
Czumaj AScheideler CYao FLuks E(2000)A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract)Proceedings of the thirty-second annual ACM symposium on Theory of computing10.1145/335305.335310(38-47)Online publication date: 1-May-2000
https://dl.acm.org/doi/10.1145/335305.335310
Show More Cited By

Index Terms

New algorithmic aspects of the Local Lemma with applications to routing and partitioning
1. Mathematics of computing
  1. Discrete mathematics
  2. Mathematical analysis
    1. Functional analysis
      1. Approximation
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems
  2. Randomness, geometry and discrete structures

Recommendations

New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning

The Lovász local lemma (LLL) is a powerful tool that is increasingly playing a valuable role in computer science. The original lemma was nonconstructive; a breakthrough of Beck and its generalizations (due to Alon and Molloy and Reed) have led to ...
A Simple Algorithmic Proof of the Symmetric Lopsided Lovász Local Lemma
Learning and Intelligent Optimization
Abstract
We provide a simple algorithmic proof for the symmetric Lopsided Lovász Local Lemma, a variant of the classic Lovász Local Lemma, where, roughly, only the degree of the negatively correlated undesirable events counts. Our analysis refers to the ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '99: Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms

January 1999

992 pages

ISBN:0898714346

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 1999

Check for updates

Qualifiers

Article

Conference

SODA99

Sponsor:

SIGACT
SIAM

SODA99: 1999 10th Conference on Discrete Algorithms

January 17 - 19, 1999

Maryland, Baltimore, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
47
Total Downloads

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

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Vöcking BVitter JSpirakis PYannakakis M(2001)Almost optimal permutation routing on hypercubesProceedings of the thirty-third annual ACM symposium on Theory of computing10.1145/380752.380848(530-539)Online publication date: 6-Jul-2001
https://dl.acm.org/doi/10.1145/380752.380848
Czumaj AScheideler CShmoys D(2000)Coloring non-uniform hypergraphsProceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms10.5555/338219.338229(30-39)Online publication date: 1-Feb-2000
https://dl.acm.org/doi/10.5555/338219.338229
Czumaj AScheideler CYao FLuks E(2000)A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract)Proceedings of the thirty-second annual ACM symposium on Theory of computing10.1145/335305.335310(38-47)Online publication date: 1-May-2000
https://dl.acm.org/doi/10.1145/335305.335310
Lu CTarjan RWarnow T(1999)A deterministic approximation algorithm for a minmax integer programming problemProceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms10.5555/314500.314888(663-668)Online publication date: 1-Jan-1999
https://dl.acm.org/doi/10.5555/314500.314888

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

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

New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning

A Simple Algorithmic Proof of the Symmetric Lopsided Lovász Local Lemma

Directed Lovász local lemma and Shearer’s lemma