Online Colored Bin Packing

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Online Colored Bin Packing

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

Online Colored Bin Packing

Popis výsledku anglicky

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

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA14-10003S" target="_blank" >GA14-10003S: Omezené typy výpočtů: algoritmy, modely, složitost</a><br>

Návaznosti

S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

APPROXIMATION AND ONLINE ALGORITHMS, WAOA 2014

ISBN

978-3-319-18263-6

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

35-46

Název nakladatele

SPRINGER-VERLAG BERLIN

Místo vydání

BERLIN

Místo konání akce

Wroclaw

Datum konání akce

11. 9. 2014

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000362517700004