Worst-case analyses, linear programming and the bin-packing problem

In this paper we consider the familiar bin-packing problem and its associated set-partitioning formulation. We show that the optimal solution to the bin-packing problem can be no larger than 4/3[Z(LP)], where Z(LP) is the optimal solution value of the linear programming relaxation ration of the set-partitioning formulation. An example is provided to show that the bound is tight. A by-product of our analysis is a new worst-case bound on the performance of the well studied First Fit Decreasing and Best Fit Decreasing heuristics, (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.