WORST-CASE ANALYSES, LINEAR-PROGRAMMING AND THE BIN-PACKING PROBLEM

Authors
CHAN LMA SIMCHILEVI D BRAMEL J
Citation
Lma. Chan et al., WORST-CASE ANALYSES, LINEAR-PROGRAMMING AND THE BIN-PACKING PROBLEM, Mathematical programming, 83(2), 1998, pp. 213-227
Citations number
12
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Computer Science Software Graphycs Programming","Operatione Research & Management Science",Mathematics,"Computer Science Software Graphycs Programming
Journal title
Mathematical programming → ACNP
ISSN journal
00255610
Volume
83
Issue
2
Year of publication
1998
Pages
213 - 227
Database
ISI
SICI code
0025-5610(1998)83:2<213:WALATB>2.0.ZU;2-A
Abstract
In this paper we consider the familiar bin-packing problem and its ass ociated set-partitioning formulation. We show that the optimal solutio n 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 relaxatio n ration of the set-partitioning formulation. An example is provided t o 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 Decr easing and Best Fit Decreasing heuristics, (C) 1998 The Mathematical P rogramming Society, Inc. Published by Elsevier Science B.V.