Set covering with ordered replacement: Additive and multiplicative gaps

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (Scopus)

Samenvatting

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.

Originele taal-2Engels
TitelInteger Programming and Combinatoral Optimization - 15th International Conference, IPCO 2011, Proceedings
Pagina's170-182
Aantal pagina's13
DOI's
StatusGepubliceerd - 2011
Extern gepubliceerdJa
Evenement15th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2011 - New York, NY, Verenigde Staten van Amerika
Duur: 15 jun. 201117 jun. 2011

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6655 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

Congres15th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2011
Land/RegioVerenigde Staten van Amerika
StadNew York, NY
Periode15/06/1117/06/11

Vingerafdruk

Duik in de onderzoeksthema's van 'Set covering with ordered replacement: Additive and multiplicative gaps'. Samen vormen ze een unieke vingerafdruk.

Citeer dit