Abstract
We consider set covering problems where the underlying set system satisfies a particular replacement property w.r.t. a given partial order on the elements: Whenever a set is in the set system then a set stemming from it via the replacement of an element by a smaller element is also in the set system.
Many variants of Bin Packing that have appeared in the literature are such set covering problems with ordered replacement. We provide a rigorous account on the additive and multiplicative integrality gap and approximability of set covering with replacement. In particular we provide a polylogarithmic upper bound on the additive integrality gap that also yields a polynomial time additive approximation algorithm if the linear programming relaxation can be efficiently solved.
We furthermore present an extensive list of covering problems that fall into our framework and consequently have polylogarithmic additive gaps as well.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Caprara, A., Kellerer, H., Pferschy, U.: Approximation schemes for ordered vector packing problems. Naval Research Logistics 50, 58–69 (2003)
Chvátal, V.: A greedy heuristic for the set-covering problem. Mathematics of Operations Research 4(3), 233–235 (1979)
Das, A., Mathieu, C., Mozes, S.: The train delivery problem- vehicle routing meets bin packing (2010)
Eisenbrand, F., Pálvölgyi, D., Rothvoß, T.: Bin packing via discrepancy of permutations. In: Symposium on Discrete Algorithms, SODA 2011. SIAM, Philadelphia (2011)
Epstein, L., Levin, A.: An APTAS for generalized cost variable-sized bin packing. SIAM Journal on Computing, 38(1) (2008)
Epstein, L., Levin, A.: Asymptotic fully polynomial approximation schemes for variants of open-end bin packing. Inf. Process. Lett. 109(1), 32–37 (2008)
Epstein, L., Levin, A.: AFPTAS results for common variants of bin packing: A new method to handle the small items. SIAM Journal on Optimization (2010) (to appear)
Epstein, L., Levin, A.: Bin packing with general cost structures. Mathematical Programming (2010) (to appear)
Feige, U.: A threshold of ln n for approximating set cover. Journal of the ACM 45(4), 634–652 (1998)
Fernandez de la Vega, W., Lueker, G.S.: Bin packing can be solved within 1 + ε in linear time. Combinatorica 1(4), 349–355 (1981)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)
Kahn, J.: Asymptotics of the chromatic index for multigraphs. Journal of Combinatorial Theory. Series B 68(2), 233–254 (1996)
Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: 23rd annual symposium on foundations of computer science (Chicago, Ill., 1982), pp. 312–320. IEEE, New York (1982)
Lovász, L.: On the ratio of optimal integral and fractional covers. Discrete Mathematics 13(4), 383–390 (1975)
Mitzenmacher, M., Upfal, E.: Probability and computing. Cambridge University Press, Cambridge (2005); Randomized algorithms and probabilistic analysis
Plantholt, M.: A sublinear bound on the chromatic index of multigraphs. Discrete Mathematics 202(1-3), 201–213 (1999)
Rothvoß, T.: The entropy rounding method in approximation algorithms (2010) (submitted)
Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)
Woeginger, G.J.: There is no asymptotic PTAS for two-dimensional vector packing. Information Processing Letters 64(6), 293–297 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Eisenbrand, F., Kakimura, N., Rothvoß, T., Sanità, L. (2011). Set Covering with Ordered Replacement: Additive and Multiplicative Gaps. In: Günlük, O., Woeginger, G.J. (eds) Integer Programming and Combinatoral Optimization. IPCO 2011. Lecture Notes in Computer Science, vol 6655. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20807-2_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-20807-2_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-20806-5
Online ISBN: 978-3-642-20807-2
eBook Packages: Computer ScienceComputer Science (R0)