Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331291 | Information Processing Letters | 2005 | 6 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Alberto Caprara, Ulrich Pferschy,