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.
Modified Subset Sum Algorithms for Bin Packing
CAPRARA, ALBERTO;
2005
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
