Lower Bounds for Online Bin Stretching with Several Bins

Result code in 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>
Result on the web
<a href="http://ceur-ws.org/Vol-1548/" target="_blank" >http://ceur-ws.org/Vol-1548/</a>
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Lower Bounds for Online Bin Stretching with Several Bins
Original language description
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.
Czech name
—
Czech description
—

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

Article name in the collection
SOFSEM-SP 2016 Student Research Forum Papers and Posters at SOFSEM 2016
ISBN
978-80-87136-22-5
ISSN
1613-0073
e-ISSN
—
Number of pages
12
Pages from-to
1-12
Publisher name
CEUR Workshop Proceedings
Place of publication
CZ
Event location
Harrachov
Event date
Jan 23, 2016
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)