Online Colored Bin Packing
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10316428" target="_blank" >RIV/00216208:11320/15:10316428 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-319-18263-6_4" target="_blank" >http://dx.doi.org/10.1007/978-3-319-18263-6_4</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-319-18263-6_4" target="_blank" >10.1007/978-3-319-18263-6_4</a>
Alternative languages
Result language
angličtina
Original language name
Online Colored Bin Packing
Original language description
In the Colored Bin Packing problem a sequence of items of sizes up to 1 arrives to be packed into bins of unit capacity. Each item has one of c }= 2 colors and an additional constraint is that we cannot pack two items of the same color next to each otherin the same bin. The objective is to minimize the number of bins. In the important special case when all items have size zero, we characterize the optimal value to be equal to color discrepancy. As our main result, we give an (asymptotically) 1.5-competitive algorithm which is optimal. In fact, the algorithm always uses at most inverted right perpendicular1.5 . OPTinverted left perpendicular bins and we show a matching lower bound of inverted right perpendicular1.5 . OPTinverted left perpendicular forany value of OPT }= 2. For items of arbitrary size we give a lower bound of 2.5 and an absolutely 3.5-competitive algorithm. We also show that classical algorithms First Fit, Best Fit and Worst Fit are not constant competitive. In the cas
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA14-10003S" target="_blank" >GA14-10003S: Restricted computations: Algorithms, models, complexity</a><br>
Continuities
S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
APPROXIMATION AND ONLINE ALGORITHMS, WAOA 2014
ISBN
978-3-319-18263-6
ISSN
0302-9743
e-ISSN
—
Number of pages
12
Pages from-to
35-46
Publisher name
SPRINGER-VERLAG BERLIN
Place of publication
BERLIN
Event location
Wroclaw
Event date
Sep 11, 2014
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000362517700004