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.2017.10
URN: urn:nbn:de:0030-drops-78514
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7851/
Balogh, Janos ;
Bekesi, Jozsef ;
Dosa, Gyorgy ;
Epstein, Leah ;
Levin, Asaf
Online Bin Packing with Cardinality Constraints Resolved
Abstract
Cardinality constrained bin packing or bin packing with cardinality constraints is a basic bin packing problem. In the online version with the parameter k >= 2, items having sizes in (0,1] associated with them are presented one by one to be packed into unit capacity bins, such that the capacities of bins are not exceeded, and no bin receives more than k items. We resolve the online problem in the sense that we prove a lower bound of 2 on the overall asymptotic competitive ratio. This closes the long standing open problem of finding the value of the best possible overall asymptotic competitive ratio, since an algorithm of an absolute competitive ratio 2 for any fixed value of k is known. Additionally, we significantly improve the known lower bounds on the asymptotic competitive ratio for every specific value of k. The novelty of our constructions is based on full adaptivity that creates large gaps between item sizes. Thus, our lower bound inputs do not follow the common practice for online bin packing problems of having a known in advance input consisting of batches for which the algorithm needs to be competitive on every prefix of the input. Last, we show a lower bound strictly larger than 2 on the asymptotic competitive ratio of the online 2-dimensional vector packing problem, and thus provide for the first time a lower bound larger than 2 on the asymptotic competitive ratio for the vector packing problem in any fixed dimension.
BibTeX - Entry
@InProceedings{balogh_et_al:LIPIcs:2017:7851,
author = {Janos Balogh and Jozsef Bekesi and Gyorgy Dosa and Leah Epstein and Asaf Levin},
title = {{Online Bin Packing with Cardinality Constraints Resolved}},
booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)},
pages = {10:1--10:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-049-1},
ISSN = {1868-8969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7851},
URN = {urn:nbn:de:0030-drops-78514},
doi = {10.4230/LIPIcs.ESA.2017.10},
annote = {Keywords: Online algorithms, bin packing, cardinality constraints, lower bounds}
}
|
Keywords: |
|
Online algorithms, bin packing, cardinality constraints, lower bounds |
|
Collection: |
|
25th Annual European Symposium on Algorithms (ESA 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
01.09.2017 |
