An Improved Lower Bound for the Bin Packing Problem
Discrete Applied Mathematics
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 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.