  guest ::
login
|
||||||||||||||
|
Search | Help | Servei de Biblioteques | Sobre el DDD | Català English Español | |||||||||
| Home > Articles > Published articles > Worst-case analyses, linear programming and the bin-packing problem |
| Date: | 1998 |
| 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|, 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. . |
| Form: | Article ; article ; publishedVersion |
| Subject: | Absolute performance ratio ; Bin-packing ; Linear programming ; Best-fit decreasing ; First-fit decreasing |
| Published in: | Mathematical Programming. Elsevier, vol. 83 n. 2 (1998) p. 213-227, ISSN 0025-5610 |
15 p, 623.1 KB  Accés restringit a la UAB |
