Lower Bounds for Online Bin Stretching with Several Bins

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10331634" target="_blank" >RIV/00216208:11320/16:10331634 - isvavai.cz</a>

Výsledek na webu

<a href="http://ceur-ws.org/Vol-1548/" target="_blank" >http://ceur-ws.org/Vol-1548/</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Lower Bounds for Online Bin Stretching with Several Bins

Popis výsledku v původním jazyce

Online Bin Stretching is a semi-online variant of Bin Packing with a set number of m bins, where all bins can be overpacked to capacity S >= 1, which is to be minimized. There is also a guarantee that an offline algorithm can pack the input to m bins of unit size. We focus on the problem of Online Bin Stretching for small m, namely 3 <= m <= 5. Recent progress on this problem has led into a lower bound of 19/14 ~ 1.357 for m = 3 and an upper bound of 11/8 ~ 1.375 for the same. For m = 4 and m = 5, only a trivial lower bound of 4/3 was known. We improve the techniques used in the previous lower bound for m = 3 to reach a lower bound of 45/33 ~ 1.36 for m=3 and a new lower bound of 19/14 ~ 1.357 for m = 4 and m = 5.

Název v anglickém jazyce

Lower Bounds for Online Bin Stretching with Several Bins

Popis výsledku anglicky

Online Bin Stretching is a semi-online variant of Bin Packing with a set number of m bins, where all bins can be overpacked to capacity S >= 1, which is to be minimized. There is also a guarantee that an offline algorithm can pack the input to m bins of unit size. We focus on the problem of Online Bin Stretching for small m, namely 3 <= m <= 5. Recent progress on this problem has led into a lower bound of 19/14 ~ 1.357 for m = 3 and an upper bound of 11/8 ~ 1.375 for the same. For m = 4 and m = 5, only a trivial lower bound of 4/3 was known. We improve the techniques used in the previous lower bound for m = 3 to reach a lower bound of 45/33 ~ 1.36 for m=3 and a new lower bound of 19/14 ~ 1.357 for m = 4 and m = 5.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2016

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

SOFSEM-SP 2016 Student Research Forum Papers and Posters at SOFSEM 2016

ISBN

978-80-87136-22-5

ISSN

1613-0073

e-ISSN

—

Počet stran výsledku

12

Strana od-do

1-12

Název nakladatele

CEUR Workshop Proceedings

Místo vydání

CZ

Místo konání akce

Harrachov

Datum konání akce

23. 1. 2016

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

WRD - Celosvětová akce

Kód UT WoS článku

—