AN IMPROVED LOWER-BOUND FOR THE BIN PACKING PROBLEM

This paper unifies and generalizes the existing lower bounds for the o ne-dimensional bin packing problem. The generalization is motivated by and based on the work of Martello and Toth (this journal, 1990), 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.