Better Algorithms for Online Bin Stretching

Kód výsledku v IS VaVaI

RIV/00216208:11320/15:10316487 - isvavai.cz

Výsledek na webu

http://dx.doi.org/10.1007/978-3-319-18263-6_3

DOI - Digital Object Identifier

10.1007/978-3-319-18263-6_3

Jazyk výsledku

angličtina

Název v původním jazyce

Better Algorithms for Online Bin Stretching

Popis výsledku v původním jazyce

Online Bin Stretching is a semi-online variant of bin packing in which the algorithm has to use the same number of bins as the optimal packing, but is allowed to slightly overpack the bins. The goal is to minimize the amount of overpacking, i.e., the maximum size packed into any bin. We give an algorithm for Online Bin Stretching with a stretching factor of 1.5 for any number of bins. We also show a specialized algorithm for three bins with a stretching factor of 11/8 = 1.375.

Název v anglickém jazyce

Better Algorithms for Online Bin Stretching

Popis výsledku anglicky

Online Bin Stretching is a semi-online variant of bin packing in which the algorithm has to use the same number of bins as the optimal packing, but is allowed to slightly overpack the bins. The goal is to minimize the amount of overpacking, i.e., the maximum size packed into any bin. We give an algorithm for Online Bin Stretching with a stretching factor of 1.5 for any number of bins. We also show a specialized algorithm for three bins with a stretching factor of 11/8 = 1.375.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

GA14-10003S: Omezené typy výpočtů: algoritmy, modely, složitost

Návaznosti

S - Specificky vyzkum na vysokych skolach
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-18262-9

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

23-34

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

000362517700003