Worst-case analyses, linear programming and the bin-packing problem
Chan, Lap Mui Ann (The Hong Kong Polytechnic University)
Simchi-Levi, David (Northwestern University)
Bramel, Julien (Columbia University)

Fecha:	1998
Resumen:	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 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.
Derechos:	Aquest material està protegit per drets d'autor i/o drets afins. Podeu utilitzar aquest material en funció del que permet la legislació de drets d'autor i drets afins d'aplicació al vostre cas. Per a d'altres usos heu d'obtenir permís del(s) titular(s) de drets.
Lengua:	Anglès
Documento:	Article ; recerca ; Versió publicada
Materia:	Absolute performance ratio ; Bin-packing ; Linear programming ; Best-fit decreasing ; First-fit decreasing
Publicado en:	Mathematical Programming, vol. 83 n. 2 (1998) p. 213-227, ISSN 0025-5610

15 p, 623.1 KB  Acceso restringido a la UAB

El registro aparece en las colecciones:
Artículos > Artículos de investigación
Artículos > Artículos publicados