Article

Free access

An extension of the Lovász local lemma, and its applications to integer programming

Author:

Aravind SrinivasanAuthors Info & Claims

SODA '96: Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms

Pages 6 - 15

Published: 28 January 1996 Publication History

PDF eReader

References

[1]

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

Google Scholar

[2]

N. Alon, The strong chromatic number of a graph, Random Structures and Algorithms, 3 (1992), pp. 1-7.

Google Scholar

[3]

N. Alon, L. Babai, and A. Itai, A fast and simple randomized parallel algorithm/or the maximal independent set problem, Journal of Algorithms, 7 (1986), pp. 567- 583.

Digital Library

Google Scholar

[4]

N. Alon, J. H. Spencer, and P. Erd6s, The Probabilistic Method, John Wiley & Sons, 1992.

Google Scholar

[5]

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

Google Scholar

[6]

J. Beck and T. Fiala, "Integer-making' theorems, Discrete Applied Mathematics, 3 (1981), pp. 1-8.

Google Scholar

[7]

J. Beck and J. H. Spencer, Integral approximation sequences, Mathematical Programming, 30 (1984), pp. 88-98.

Google Scholar

[8]

B. Berger and J. Rompel, Simulating ~ogCn)-wise independence in NC, JACM, 38 (1991), pp. 1026-1046.

Digital Library

Google Scholar

[9]

R. B. Boppana and J. H. Spencer, A useful elementary correlation inequality, Journal of Combinatorial Theory, Series A, 50 (1989), pp. 305-307.

Digital Library

Google Scholar

[10]

V. Chv~tal, A greedy heuristic for the set covering problem, Math. of O.R., 4 (1979), pp. 233-235.

Google Scholar

[11]

G. Dobson, Worst-case analysis of greedy heuristics for integer programming with nonnegative data, Math. of O.R., 7 (1982), pp. 515-531.

Google Scholar

[12]

M. L. Fisher and L. A. Wolsey, On the greedy heuristic for continuous covering and packing problems, SIAM J. on Algebraic and Discrete Methods, 3 (1982), pp. 584-591.

Google Scholar

[13]

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

Google Scholar

[14]

C. M. Fortuin, J. Ginibre, and P. N. Kasteleyn, Correlational inequalities for partially ordered sets, Communications of Mathematical Physics, 22 (1971), pp. 89-103.

Google Scholar

[15]

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

Google Scholar

[16]

S. Janson, T. Luczak and A. Rucinski, An exponential bound for the probability of nonexistence of a specified subgraph in a random graph, In Random Graphs '87, Karonski et al., eds., John Wiley & Sons, Chichester, 1990, pp. 73-87.

Google Scholar

[17]

H. J. Karloff and D. B. Shmoys, Efficient parallel algorithms for edge coloring problems, Journal of Algorithms, 8 (1987), pp. 39-52.

Digital Library

Google Scholar

[18]

R. M. Karp, F. T. Leighton, R. L. Rivest, C. D. Thompson, U. V. Vazirani, and V. V. Vazirani, Global wire routing in two-dimensional arrays, Algorithmica, 2 (1987), pp. 113-129.

Google Scholar

[19]

F. T. Leighton, B. Maggs, and S. B. Rao, Packet routing and jobshop scheduling in O( congestion 4~ dilation) steps, Combinatorica, 14 (1994), pp. 167-186.

Google Scholar

[20]

F. T. Leighton and B. Maggs, Fast algorithm~ for finding O(congestion-/-dilation) packet routing schedules, Manuscript, 1995.

Google Scholar

[21]

L. Lovgsz, On the ratio of optimal integral and fractional covers, Discrete Math., 13 (1975), pp. 383-390.

Google Scholar

[22]

M. Luby, A simple parallel algorithm for the maximal independent set problem, SIAM J. Comput., 15 (1986), pp. 1036-1053.

Digital Library

Google Scholar

[23]

R. Motwani, J. Naor, and M. Naor, The probabilistic method yields dete~ninistic parallel algorithms, Journal of Computer and System Sciences, 49 (1994), pp. 478- 516.

Digital Library

Google Scholar

[24]

N. Nisan, Pseudorandom generators for space-bounded computation, Combinatorica, 12 (1992!, pp. 449-461.

Google Scholar

[25]

S. A. Plotkin, D. B. Shmoys, and E. Tardos, Fast approximation algorithms for fractional packing and covering problems, In Proc. IEEE FOGS Symposium, pp. 495-504, 199t.

Digital Library

Google Scholar

[26]

P. Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, 37 (1988), pp. 130-143.

Digital Library

Google Scholar

[27]

P. Raghavan and (3. D. Thompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, 7 (1987), pp. 365-374.

Digital Library

Google Scholar

[28]

T. K. Sarkar. Some lower bounds of reliability, Technical Report 124, Department of Operations Research and Statistics, Stanford University, 1969.

Google Scholar

[29]

J. P. Schmidt, A. Siegel, and A. Srinivasan, Cher~off- Hoeffding bounds for applications with limited independence, S{AM Journal on Discrete Mathematics, 8 (1995), pp. 223-250.

Digital Library

Google Scholar

[30]

J. H. Spencer, Ten Lectures on the Probabilistic Method, SIAM, Philadelphia, 1987.

Google Scholar

[31]

A. Srinivasan, Improved approximations of packing and covering problems, In Proc. A CM Symposium on Theory of Computing, pp. 268-276, 1995.

Digital Library

Google Scholar

Cited By

View all

Ran YShi YZhang Z(2017)Local ratio method on partial set multi-coverJournal of Combinatorial Optimization10.1007/s10878-016-0066-034:1(302-313)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1007/s10878-016-0066-0
Ran YZhang ZDu HZhu Y(2017)Approximation algorithm for partial positive influence problem in social networkJournal of Combinatorial Optimization10.1007/s10878-016-0005-033:2(791-802)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1007/s10878-016-0005-0
Knoche JKrysta P(2006)An experimental study of the misdirection algorithm for combinatorial auctionsProceedings of the 4th international conference on Approximation and Online Algorithms10.1007/11970125_21(265-278)Online publication date: 14-Sep-2006
https://dl.acm.org/doi/10.1007/11970125_21
Show More Cited By

Index Terms

An extension of the Lovász local lemma, and its applications to integer programming
1. Mathematics of computing
  1. Discrete mathematics
  2. Mathematical analysis
    1. Mathematical optimization
      1. Mixed discrete-continuous optimization
        Integer programming
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems
    2. Mathematical optimization
      1. Mixed discrete-continuous optimization
        Integer programming
  2. Randomness, geometry and discrete structures

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 ...
A Kolmogorov complexity proof of the Lovász Local Lemma for satisfiability

The Lovasz Local Lemma provides a syntactic property that a Boolean formula is satisifiable. Moser and Tardos came up with a constructive proof of the lemma, i.e. the proof gives a method to actually construct a satisfying assignment. In this paper, we ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '96: Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms

January 1996

586 pages

ISBN:0898713668

Chairman:
Éva Tardos

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 28 January 1996

Check for updates

Qualifiers

Article

Conference

SODA96

Sponsor:

SIGACT
SIAM

SODA96: Conference on Discrete Algorithms

January 28 - 30, 1996

Georgia, Atlanta, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
449
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)8

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ran YShi YZhang Z(2017)Local ratio method on partial set multi-coverJournal of Combinatorial Optimization10.1007/s10878-016-0066-034:1(302-313)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1007/s10878-016-0066-0
Ran YZhang ZDu HZhu Y(2017)Approximation algorithm for partial positive influence problem in social networkJournal of Combinatorial Optimization10.1007/s10878-016-0005-033:2(791-802)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1007/s10878-016-0005-0
Knoche JKrysta P(2006)An experimental study of the misdirection algorithm for combinatorial auctionsProceedings of the 4th international conference on Approximation and Online Algorithms10.1007/11970125_21(265-278)Online publication date: 14-Sep-2006
https://dl.acm.org/doi/10.1007/11970125_21
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
Kolliopoulos SYoung N(2005)Approximation algorithms for covering/packing integer programsJournal of Computer and System Sciences10.1016/j.jcss.2005.05.00271:4(495-505)Online publication date: 1-Nov-2005
https://dl.acm.org/doi/10.1016/j.jcss.2005.05.002
Kolliopoulos SStein C(2004)Approximating disjoint-path problems using packing integer programsMathematical Programming: Series A and B10.1007/s10107-002-0370-699:1(63-87)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.1007/s10107-002-0370-6
Shachnai HShmueli OSayegh R(2004)Approximation schemes for deal splitting and covering integer programs with multiplicity constraintsProceedings of the Second international conference on Approximation and Online Algorithms10.1007/978-3-540-31833-0_11(111-125)Online publication date: 14-Sep-2004
https://dl.acm.org/doi/10.1007/978-3-540-31833-0_11
Kolliopoulos S(2003)Approximating covering integer programs with multiplicity constraintsDiscrete Applied Mathematics10.1016/S0166-218X(02)00598-X129:2-3(461-473)Online publication date: 1-Aug-2003
https://dl.acm.org/doi/10.1016/S0166-218X%2802%2900598-X
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

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

Directed Lovász local lemma and Shearer’s lemma

Deterministic algorithms for the Lovász Local Lemma

A Kolmogorov complexity proof of the Lovász Local Lemma for satisfiability