ISSN:
1432-0541
Keywords:
Average-case analysis
;
Cutting stock problems
;
Two-dimensional packing
;
Bin packing
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract New approximation algorithms for packing rectangles into a semi-infinite strip are introduced in this paper. Within a standard probability model, an asymptotic average-case analysis is given for the wasted space in the packings produced by these algorithms. An off-line algorithm is presented along with a proof that it wastes θ(√/n)space on the average, wheren is the number of rectangles packed. This result is known to apply to optimal packings as well. Several on-line shelf algorithms are also analyzed. Withn assumed known in advance, one such algorithm is described and shown to waste θ(n 2/3) space on the average. It is proved that this result also characterizes optimal on-line shelf packings. For a very general class of linear-time algorithms, it is shown that a constant (nonzero) fraction of the space must be wasted on the average for alln, and a lower bound on this fraction in terms of algorithm parameters is given. Finally, the paper discusses the implications of the above results for dynamic packing and two-dimensional bin-packing problems.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01190899
Permalink