Set covering with ordered replacement: Additive and multiplicative gaps

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

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.

Original languageEnglish
Title of host publicationInteger Programming and Combinatoral Optimization - 15th International Conference, IPCO 2011, Proceedings
Pages170-182
Number of pages13
DOIs
Publication statusPublished - 2011
Externally publishedYes
Event15th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2011 - New York, NY, United States
Duration: 15 Jun 201117 Jun 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6655 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2011
CountryUnited States
CityNew York, NY
Period15/06/1117/06/11

Fingerprint Dive into the research topics of 'Set covering with ordered replacement: Additive and multiplicative gaps'. Together they form a unique fingerprint.

  • Cite this

    Eisenbrand, F., Kakimura, N., Rothvoß, T., & Sanità, L. (2011). Set covering with ordered replacement: Additive and multiplicative gaps. In Integer Programming and Combinatoral Optimization - 15th International Conference, IPCO 2011, Proceedings (pp. 170-182). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6655 LNCS). https://doi.org/10.1007/978-3-642-20807-2_14