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...
Elmentve itt :
| Szerzők: | |
|---|---|
| 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 |
| LEADER | 01606nab a2200289 i 4500 | ||
|---|---|---|---|
| 001 | publ28438 | ||
| 005 | 20231017145812.0 | ||
| 008 | 231017s2020 hu o 0|| Angol d | ||
| 022 | |a 0302-9743 | ||
| 024 | 7 | |a 10.1007/978-3-030-39479-0_2 |2 doi | |
| 024 | 7 | |a 31141043 |2 mtmt | |
| 040 | |a SZTE Publicatio Repozitórium |b hun | ||
| 041 | |a Angol | ||
| 100 | 1 | |a Balogh János | |
| 245 | 1 | 2 | |a A New Lower Bound for Classic Online Bin Packing |h [elektronikus dokumentum] / |c Balogh János |
| 260 | |c 2020 | ||
| 300 | |a 18-28 | ||
| 490 | 0 | |a LECTURE NOTES IN COMPUTER SCIENCE |v 11926 | |
| 520 | 3 | |a 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. | |
| 650 | 4 | |a Számítás- és információtudomány | |
| 700 | 0 | 1 | |a Békési József |e aut |
| 700 | 0 | 1 | |a Dósa György |e aut |
| 700 | 0 | 1 | |a Epstein Leah |e aut |
| 700 | 0 | 1 | |a Levin Asaf |e aut |
| 856 | 4 | 0 | |u http://publicatio.bibl.u-szeged.hu/28438/4/978-3-030-39479-0_2.pdf |z Dokumentum-elérés |
| 856 | 4 | 0 | |u http://publicatio.bibl.u-szeged.hu/28438/3/31141043_c%C3%ADmlap_tartalom.pdf |z Dokumentum-elérés |
| 856 | 4 | 0 | |u http://publicatio.bibl.u-szeged.hu/28438/1/NewLowerBoundONlineBP.pdf |z Dokumentum-elérés |