Modified subset sum heuristics for bin packing. (English) Zbl 1184.68661
Summary: 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.
Software:
KnapsackReferences:
| [1] | Caprara, A.; Kellerer, H.; Pferschy, U.; Pisinger, D., Approximation algorithms for knapsack problems with cardinality constraints, European J. Oper. Res., 123, 333-345 (2000) · Zbl 0961.90131 |
| [2] | Caprara, A.; Pferschy, U., Worst-case analysis of the subset sum algorithm for bin packing, Oper. Res. Lett., 32, 159-166 (2004) · Zbl 1060.90061 |
| [3] | Coffman, E. G.; Garey, M. R.; Johnson, D. S., Approximation algorithms for bin-packing: a survey, (Hochbaum, D. S., Approximation Algorithms for NP-Hard Problems (1997), PWS Publishing Company: PWS Publishing Company Boston, MA), 46-93 |
| [4] | Friesen, D. K.; Langston, M. A., Analysis of a compound bin-packing algorithm, SIAM J. Discrete Math., 4, 61-79 (1991) · Zbl 0714.68033 |
| [5] | Fleszar, K.; Hindi, K. S., New heuristics for one-dimensional bin-packing, Comput. Oper. Res., 29, 821-839 (2002) · Zbl 0994.90134 |
| [6] | Garey, M. R.; Graham, R. L.; Ullman, J. D., An analysis of some packing algorithms, (Rustin, R., Combinatorial Algorithms (1973), Algorithmics Press: Algorithmics Press New York), 39-47 |
| [7] | R.L. Graham, Bounds on multiprocessing anomalies and related packing algorithms, in: Proc. 1972 Spring Joint Computer Conference, 1972, pp. 205-217; R.L. Graham, Bounds on multiprocessing anomalies and related packing algorithms, in: Proc. 1972 Spring Joint Computer Conference, 1972, pp. 205-217 |
| [8] | Gupta, J. N.D.; Ho, J. C., A new heuristic algorithm for the one-dimensional bin-packing problem, Production Planning and Control, 10, 598-603 (1999) |
| [9] | D.S. Johnson, Near-optimal bin packing algorithms, PhD Thesis, Massachusetts Institute of Technology, 1973; D.S. Johnson, Near-optimal bin packing algorithms, PhD Thesis, Massachusetts Institute of Technology, 1973 |
| [10] | Kellerer, H.; Pferschy, U.; Pisinger, D., Knapsack Problems (2004), Springer: Springer Berlin · Zbl 1103.90003 |
| [11] | Pferschy, U., Dynamic programming revisited: Improving knapsack algorithms, Computing, 63, 419-430 (1999) · Zbl 0946.90053 |
| [12] | Pisinger, D., Linear time algorithms for knapsack problems with bounded weights, J. Algorithms, 33, 1-14 (1999) · Zbl 0951.90047 |
| [13] | Vanderbeck, F., Computational study of a column generation algorithm for bin packing and cutting stock problems, Math. Programming, 86, 565-594 (1999) · Zbl 0949.90066 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
