Two-dimensional rectangle packing: on-line methods and results
The first algorithms for the on-line two-dimensional rectangle packing problem were introduced by Coppersmith and Raghavan. They showed that for a family of heuristics 13/4 is an upper bound for the asymptotic worst-case ratios. We have investigated the Next Fit and the First Fit variants of their method. We proved that the asymptotic worst-case ratio equals 13/4 for the Next Fit variant and that 49/16 is an upper bound of the asymptotic worst-case ratio for the First Fit variant.
Year of publication: |
1993-09-03
|
---|---|
Authors: | Csirik, J. ; Frenk, J.B.G. ; Labbé, M. |
Institutions: | Erasmus University Rotterdam, Econometric Institute |
Saved in:
freely available
Extent: | application/pdf |
---|---|
Series: | Econometric Institute Report. - ISSN 1566-7294. |
Type of publication: | Book / Working Paper |
Notes: | The text is part of a series RePEc:dgr:eureir Number 1765011700 |
Source: |
Persistent link: https://www.econbiz.de/10004998894
Saved in favorites
Similar items by person
-
On the multidimensional vector bin packing
Frenk, J.B.G., (1990)
-
A note on a stochastic location problem
Frenk, J.B.G., (1993)
-
Improved algorithms for machine allocation in manufacturing systems
Frenk, J.B.G., (1994)
- More ...