CRIS Current Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishWe analyze the worst-case ratio of a natural heuristic for the bin packing problem, which proceeds by filling one bin at a time, each as much as possible. A known lower bound on the worst-case ratio of this heuristic is 1.6067..., conjectured to be tight. In this paper, we show a nontrivial upper bound of 4/3 + ln (4/3) = 1.6210..., thus determining the value of the worst-case ratio within a relative error smaller than 1%. We also discuss how the lower and upper bounds extend to the case in which the maximum item size is bounded.
| Titolo: | Worst-Case Analysis of the Subset Sum Algorithm for Bin Packing |
| Autore/i: | CAPRARA, ALBERTO; U. PFERSCHY |
| Autore/i Unibo: | |
| Anno: | 2004 |
| Rivista: | |
| Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/S0167-6377(03)00092-0 |
| Abstract: | We analyze the worst-case ratio of a natural heuristic for the bin packing problem, which proceeds by filling one bin at a time, each as much as possible. A known lower bound on the worst-case ratio of this heuristic is 1.6067..., conjectured to be tight. In this paper, we show a nontrivial upper bound of 4/3 + ln (4/3) = 1.6210..., thus determining the value of the worst-case ratio within a relative error smaller than 1%. We also discuss how the lower and upper bounds extend to the case in which the maximum item size is bounded. |
| Data prodotto definitivo in UGOV: | 2005-10-13 14:35:51 |
| Appare nelle tipologie: | 1.01 Articolo in rivista |
File in questo prodotto:
http://hdl.handle.net/11585/1110
Copyright © 2020