Two-dimensional rectangle packing: on-line methods and results
1993-09-03
Article
volume 45, issue 3 pp 197-204.
This publication is part of collection
| Related Files |
|---|
View PDF Version
(Two-dimensional_rectangle_packing.pdf, 0.5MB) |
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.
Automatically Extracted Terms
- strip
- rectangle
- height
- width
- algorithm
- heuristic
- type -2 item
- type -2
- type -3 items
- type -3 item
- problem
- type-l item
- type-l
- ratio
- raghavan
- number
- method
- csirik
- coppersmith
- type-l items
