Worst-case analyses, linear programming and the bin-packing problem |
| |
Authors: | Lap Mui Ann Chan David Simchi-Levi Julien Bramel |
| |
Affiliation: | (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 等数据库收录! |
|