×

Lower bounds and reduction procedures for the bin packing problem. (English) Zbl 0704.90074

Summary: The bin packing problem, in which a set of items of various sizes has to be packed into a minimum number of identical bins, has been extensively studied during the past fifteen years, mainly with the aim of finding fast heuristic algorithms to provide good approximate solutions. We present lower bounds and a dominance criterion and derive a reduction algorithm. Lower bounds are evaluated through an extension of the concept of worst-case performance. For both lower bounds and reduction algorithm an experimental analysis is provided.

MSC:

90C27 Combinatorial optimization
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Coffman, E. G.; Garey, M. R.; Johnson, D. S., Approximation algorithms for bin-packing—An updated survey, (Ausiello, G.; Lucertini, M.; Serafini, P., Algorithm Design for Computer System Design (1984), Springer: Springer Vienna) · Zbl 0558.68062
[2] Eilon, S.; Christofides, N., The loading problem, Management Sci., 17, 259-267 (1971) · Zbl 0208.45701
[3] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039
[4] Hung, M. S.; Brown, J. R., An algorithm for a class of loading problems, Naval Res. Logist. Quart., 25, 289-297 (1978) · Zbl 0404.90057
[5] Johnson, D. S., Near-optimal bin packing algorithms, Doctoral Thesis (1973), Department of Mathematics, Massachussets Institute of Technology: Department of Mathematics, Massachussets Institute of Technology Cambridge, MA
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.