Worst-case analyses, linear programming and the bin-packing problem |
| |
| Authors: | Lap Mui Ann Chan David Simchi-Levi Julien Bramel |
| |
| Institution: | (1) Department of Management, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong People's Republic of China;(2) Department of Industrial Engineering and Management Sciences, Northwestern University, MLSB 2225 North Campus Drive, 60208-3119 Evanston, IL, USA;(3) Graduate School of Business, Columbia University, 10027 New York, NY, USA |
| |
| Abstract: | 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⌉, whereZ
LP is the optimal solution value of the linear programming relaxation 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.
This research was supported in part by ONR Contracts N00014-90-J-1649 and N00014-95-1-0232, and NSF Contracts DDM-8922712
and DDM-9322828. |
| |
| Keywords: | Absolute performance ratio Bin-packing Linear programming Best-fit decreasing First-fit decreasing |
| 本文献已被 SpringerLink 等数据库收录！ |
|
