[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Randomized approximation of bounded multicovering problems

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

The problem of finding approximate solutions for a subclass of multicovering problems denoted byILP(k, b) is considered. The problem involves findingx∈{0,1}n that minimizes ∑ j x j subject to the constraintAx≥b, whereA is a 0–1m×n matrix with at mostk ones per row,b is an integer vector, andb is the smallest entry inb. This subclass includes, for example, the Bounded Set Cover problem whenb=1, and the Vertex Cover problem whenk=2 andb=1.

An approximation ratio ofk−b+1 is achievable by known deterministic algorithms. A new randomized approximation algorithm is presented, with an approximation ratio of (k−b+1)(1−(c/m)1/(k−b+1)) for a small constantc>0. The analysis of this algorithm relies on the use of a new bound on the sum of independent Bernoulli random variables, that is of interest in its own right.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • [ALM+] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximating problems. InProc. 33rd IEEE Symp. on Foundations of Computer Science, pages. 14–23, 1992.

  • [BE] R. Bar-Yehuda and S. Even. A local-ratio theorem for approximating the weighted vertex cover problem.Ann. Discrete Math., 25:27–46, 1985.

    MATH  MathSciNet  Google Scholar 

  • [BKP1] J. Bar-Ilan, G. Kortsarz, and D. Peleg. Greedy approximation algorithms. Technical Report CS92-28, The Weizmann Institute of Science, Rehovot, 1992.

    Google Scholar 

  • [BKP2] J. Bar-Ilan, G. Kortsarz, and D. Peleg. How to allocate network centers.J. Algorithms, 15: 385–415, 1993.

    Article  MATH  MathSciNet  Google Scholar 

  • [BV] D. Bertsimas and R. Vohra. Linear programming relaxations, approximation algorithms and randomization: a unified view of covering problems, Working Paper, Operations Research Center, MIT, Cambridge, MA, 1994.

    Google Scholar 

  • [Che] H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.Ann. Math. Statist., 23:493–509, 1952.

    MATH  MathSciNet  Google Scholar 

  • [Chu] K. L. Chung.A Course in Probability Theory. Academic Press, New York, 1974.

    MATH  Google Scholar 

  • [Chv] V. Chvatal. A greedy heuristic for the set-covering problem.Math. Oper. Res., 4(3):233–235, 1979.

    MATH  MathSciNet  Google Scholar 

  • [D] G. Dobson. Worst case analysis of greedy heuristics for integer programming with nonnegative data.Math. Oper. Res., 7:515–531, 1982.

    Article  MATH  MathSciNet  Google Scholar 

  • [F] U. Feige. Personal communication, 1993.

  • [GJ] M. R. Garey and D. S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979.

    MATH  Google Scholar 

  • [GW] T. Grossman and A. Wool. Computational experience with approximation algorithms for the set covering problem.Euro. J. Operational Research, To appear. See also, Technical Report CS94-25, The Weizmann Institute of Science, Rehovot.

  • [HH] N. G. Hall and D. S. Hochbaum. A fast approximation algorithm for the multicovering problem.Discrete Appl. Math., 15:35–40, 1986.

    Article  MATH  MathSciNet  Google Scholar 

  • [Hoc1] D. S. Hochbaum. Approximation algorithms for the set covering and vertex cover problems.SIAM J. Comput., 11(3):555–556, 1982.

    Article  MATH  MathSciNet  Google Scholar 

  • [Hoc2] D. S. Hochbaum. Efficient bounds for the stable set, vertex cover, and set packing problems.Discrete Appl. Math., 6:243–254, 1983.

    Article  MATH  MathSciNet  Google Scholar 

  • [Hoc3] D. S. Hochbaum. On the fractional solution to the set covering problem.SIAM J. Algebraic Discrete Methods, 4(2):221–222, 1983.

    MATH  MathSciNet  Google Scholar 

  • [HS] D. S. Hochbaum and D. B. Shmoys. A unified approach to approximation algorithms for bottleneck problems.J. Assoc. Comput. Mach., 33(3):533–550, July 1986.

    MathSciNet  Google Scholar 

  • [J] D. S. Johnson. Approximation algorithms for combinatorial problems.J. Comput. System Sci., 9:256–278, 1974.

    Article  MATH  MathSciNet  Google Scholar 

  • [Kar] N. Karmarkar. A new polynomial-time algorithm for linear programming.Combinatorica, 4:373–395, 1984.

    MATH  MathSciNet  Google Scholar 

  • [Kha] L. G. Khachiyan. A polynomial algorithm in linear programming.Dokl. Akad. Nauk SSSR, 244(S):1093–1096, 1979. Translated inSoviet Math. Dokl., 20(1):191–194, 1979.

    MATH  MathSciNet  Google Scholar 

  • [L] L. Lovász. On the ratio of optimal integral and fractional covers.Discrete Math., 13:383–390, 1975.

    Article  MATH  MathSciNet  Google Scholar 

  • [NT] G. L. Nemhauser and L. E. Trotter. Vertex packing: Structural properties and algorithms.Math. Programming, 8:232–248, 1975.

    Article  MATH  MathSciNet  Google Scholar 

  • [PSW] D. Peleg, G. Schechtman, and A. Wool. Approximating bounded 0–1 integer linear programs. InProc. 2nd Israel Symp. on Theory of Computing Systems, pages 69–77, Netanya, 1993.

  • [PY] C. H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes.J. Comput. System Sci., 43:425–440, 1991.

    Article  MATH  MathSciNet  Google Scholar 

  • [R] P. Raghavan. Probabilistic construction of deterministic algorithms: approximating packing integer programs.J. Comput. System Sci., 37:130–143, 1988.

    Article  MATH  MathSciNet  Google Scholar 

  • [RT] P. Raghavan and C. D. Thompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs.Combinatorica, 7(4):365–374, 1987.

    MATH  MathSciNet  Google Scholar 

  • [Wol] L. A. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem.Combinatorica, 2:385–393, 1982.

    MATH  MathSciNet  Google Scholar 

  • [Woo] A. Wool. Approximating bounded 0–1 integer linear programs. Master’s thesis, Department of Applied Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, 1992.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Applied Mathematics and Computer Science, The Weizmann Institute, 76100, Rehovot, Israel

    D. Peleg

  2. Department of Theoretical Mathematics, The Weizmann Institute, 76100, Rehovot, Israel

    G. Schechtman

  3. Bell Laboratories, 700 Mountain Avenue, 07974, Murray Hill, NJ, USA

    A. Wool

Authors
  1. D. Peleg
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. G. Schechtman
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. A. Wool
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by M. X. Goemans.

The first author was supported in part by a Walter and Elise Haas Career Development Award and by a grant from the Israeli Science Foundation. This work was done white the third author was at the Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, Israel.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Peleg, D., Schechtman, G. & Wool, A. Randomized approximation of bounded multicovering problems. Algorithmica 18, 44–66 (1997). https://doi.org/10.1007/BF02523687

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02523687

Key Words

Search

Navigation