Title

An Improved Lower Bound for the Bin Packing Problem

Document Type

Article

Publication Date

1996

Source Publication

Discrete Applied Mathematics

Abstract

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.

Comments

Discrete Applied Mathematics, Volume 66, Issue 1, pp 81-94 (April, 1996). DOI: 10.1016/0166-218X(96)80459-8