zbMATH — the first resource for mathematics

An improved lower bound for the bin packing problem. (English) Zbl 0853.90094
Summary: This paper unifies and generalizes the existing lower bounds for the one-dimensional bin packing problem. The generalization is motivated by and based on the work of S. Martello and P. Toth [Discrete Appl. Math. 28, No. 1, 59-70 (1990; Zbl 0704.90074)]. The worst-case performance of the unified lower bound is analyzed and two new lower bounds are proposed and compared with existing lower bounds through numerical experiments.

90C27 Combinatorial optimization
Full Text: DOI
[1] Coffman, E.G; Garey, M.R; Johnson, D.S, Approximation algorithms for bin-packing — an updated survey, () · Zbl 0558.68062
[2] Garey, M.R; Johnson, D.S, Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[3] Kim, Y.-D; Yano, C.A, Heuristic approaches for loading problems in flexible manufacturing systems, IIE trans., 25, 26-39, (1993)
[4] Martello, S; Toth, P, Lower bounds and reduction procedures for the bin packing problem, Discrete appl. math., 28, 59-70, (1990) · Zbl 0704.90074
[5] Martello, S; Toth, P, Knapsack problems: algorithms and computer implementations, (1990), Wiley New York · Zbl 0708.68002
[6] Ong, H.L; Magazine, M.J; Wee, T.S, Probabilistic analysis of bin packing heuristics, Oper. res., 32, 983-998, (1984) · Zbl 0551.90067
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.