A New Lower Bound for Classic Online Bin Packing

We improve the lower bound on the asymptotic competitive ratio of any online algorithm for bin packing to above 1.54278. We demonstrate for the first time the advantage of branching and the applicability of full adaptivity in the design of lower bounds for the classic online bin packing problem. We...

Teljes leírás

Elmentve itt :
Bibliográfiai részletek
Szerzők: Balogh János
Békési József
Dósa György
Epstein Leah
Levin Asaf
Dokumentumtípus: Cikk
Megjelent: 2020
Sorozat:LECTURE NOTES IN COMPUTER SCIENCE 11926
Tárgyszavak:
doi:10.1007/978-3-030-39479-0_2

mtmt:31141043
Online Access:http://publicatio.bibl.u-szeged.hu/28438
Leíró adatok
Tartalmi kivonat:We improve the lower bound on the asymptotic competitive ratio of any online algorithm for bin packing to above 1.54278. We demonstrate for the first time the advantage of branching and the applicability of full adaptivity in the design of lower bounds for the classic online bin packing problem. We apply a new method for weight based analysis, which is usually applied only in proofs of upper bounds. The values of previous lower bounds were approximately 1.5401 and 1.5403. © 2020, Springer Nature Switzerland AG.
Terjedelem/Fizikai jellemzők:18-28
ISSN:0302-9743