License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.18
URN: urn:nbn:de:0030-drops-111391
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11139/
Berndt, Sebastian ;
Epstein, Leah ;
Jansen, Klaus ;
Levin, Asaf ;
Maack, Marten ;
Rohwedder, Lars
Online Bin Covering with Limited Migration
Abstract
Semi-online models where decisions may be revoked in a limited way have been studied extensively in the last years.
This is motivated by the fact that the pure online model is often too restrictive to model real-world applications, where some changes might be allowed. A well-studied measure of the amount of decisions that can be revoked is the migration factor beta: When an object o of size s(o) arrives, the decisions for objects of total size at most beta * s(o) may be revoked. Usually beta should be a constant. This means that a small object only leads to small changes. This measure has been successfully investigated for different, classical problems such as bin packing or makespan minimization. The dual of makespan minimization - the Santa Claus or machine covering problem - has also been studied, whereas the dual of bin packing - the bin covering problem - has not been looked at from such a perspective.
In this work, we extensively study the bin covering problem with migration in different scenarios. We develop algorithms both for the static case - where only insertions are allowed - and for the dynamic case, where items may also depart. We also develop lower bounds for these scenarios both for amortized migration and for worst-case migration showing that our algorithms have nearly optimal migration factor and asymptotic competitive ratio (up to an arbitrary small epsilon). We therefore resolve the competitiveness of the bin covering problem with migration.
BibTeX - Entry
@InProceedings{berndt_et_al:LIPIcs:2019:11139,
author = {Sebastian Berndt and Leah Epstein and Klaus Jansen and Asaf Levin and Marten Maack and Lars Rohwedder},
title = {{Online Bin Covering with Limited Migration}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {18:1--18:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-124-5},
ISSN = {1868-8969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11139},
URN = {urn:nbn:de:0030-drops-111391},
doi = {10.4230/LIPIcs.ESA.2019.18},
annote = {Keywords: online algorithms, dynamic algorithms, competitive ratio, bin covering, migration factor}
}
|
Keywords: |
|
online algorithms, dynamic algorithms, competitive ratio, bin covering, migration factor |
|
Collection: |
|
27th Annual European Symposium on Algorithms (ESA 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
06.09.2019 |
