Set Covering with Ordered Replacement: Additive and Multiplicative Gaps

DOI10.1007/978-3-642-20807-2_14MaRDI QIDQ3009761zbMATH OpenOpenAlexFDO

Authors Friedrich Eisenbrand, Naonori Kakimura, Thomas Rothvoß, Laura Sanità

Publication date 24 June 2011

Published in Integer Programming and Combinatoral Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.3295

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Combinatorial aspects of packing and covering (05B40)

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.

Recommendations

• Covering sets by subsets
• Set multi-covering via inclusion-exclusion
• scientific article; zbMATH DE number 3865329
• Covering a poset by interval orders
• Covering a set by subsets
• Covering arrays via set covers
• A dissection of the duality gap of set covering problems
• Covering by discrete and closed discrete sets
• The ordered covering problem
• Problems and algorithms for covering arrays via set covers

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• A sublinear bound on the chromatic index of multigraphs
• A threshold of ln n for approximating set cover
• AFPTAS results for common variants of bin packing: a new method for handling the small items
• An APTAS for Generalized Cost Variable-Sized Bin Packing
• Approximation schemes for ordered vector packing problems
• Asymptotic fully polynomial approximation schemes for variants of open-end bin packing
• Asymptotics of the chromatic index for multigraphs
• Bin packing can be solved within 1+epsilon in linear time
• Bin packing with general cost structures
• On the ratio of optimal integral and fractional covers
• Probability and Computing
• The train delivery problem -- vehicle routing meets bin packing
• There is no asymptotic PTAS for two-dimensional vector packing

Cited in

(2)

• A new integer programming formulation of the graphical traveling salesman problem
• The entropy rounding method in approximation algorithms

This page was built for publication: Set Covering with Ordered Replacement: Additive and Multiplicative Gaps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3009761)