TY - GEN
T1 - Set covering with ordered replacement
T2 - 15th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2011
AU - Eisenbrand, Friedrich
AU - Kakimura, Naonori
AU - Rothvoß, Thomas
AU - Sanità, Laura
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=79959977326&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79959977326&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-20807-2_14
DO - 10.1007/978-3-642-20807-2_14
M3 - Conference contribution
AN - SCOPUS:79959977326
SN - 9783642208065
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 170
EP - 182
BT - Integer Programming and Combinatoral Optimization - 15th International Conference, IPCO 2011, Proceedings
Y2 - 15 June 2011 through 17 June 2011
ER -