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 natural variations of the so-called subset sum heuristic for the bin packing problem, which proceeds by filling one bin at a time, each as much as possible. Namely, we consider the variation in which the largest remaining item is packed in the current bin, and then the remaining capacity is filled as much as possible, as well as the variation in which all items larger than half the capacity are first packed in separate bins, and then the remaining capacity is filled as much as possible. For both variants, we show a nontrivial upper bound of 13/9 on the worst-case ratio, also discussing lower bounds on this ratio.
| Titolo: | Modified Subset Sum Algorithms for Bin Packing | |
| Autore/i: | CAPRARA, ALBERTO; U. Pferschy | |
| Autore/i Unibo: | ||
| Anno: | 2005 | |
| Rivista: | ||
| Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.ipl.2005.04.005 | |
| Abstract: | We analyze the worst-case ratio of natural variations of the so-called subset sum heuristic for the bin packing problem, which proceeds by filling one bin at a time, each as much as possible. Namely, we consider the variation in which the largest remaining item is packed in the current bin, and then the remaining capacity is filled as much as possible, as well as the variation in which all items larger than half the capacity are first packed in separate bins, and then the remaining capacity is filled as much as possible. For both variants, we show a nontrivial upper bound of 13/9 on the worst-case ratio, also discussing lower bounds on this ratio. | |
| Data prodotto definitivo in UGOV: | 2005-10-13 16:32:41 | |
| Appare nelle tipologie: | 1.01 Articolo in rivista |
File in questo prodotto:
http://hdl.handle.net/11585/17227
Copyright © 2021