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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Baker, B. S., and Schwarz, J. S., Shelf Algorithms for Two-Dimensional Packing Problems,SIAM J. Comput.,12 (1983), 508–525.
Bartholdi, J. J., Vande Vate, J. H., and Zhang, J., Expected Performance of the Shelf Heuristic for Two-Dimensional Packing,Oper. Res. Lett.,8 (1989), 11–16.
Coffman, E. G., Jr., Flatto, L., and Leighton, F. T., First-Fit Allocation of Queues: Tight Probabilistic Bounds on Wasted Space,Stochastic Process Appl.,36 (1990), 311–330.
Coffman, E. G., Jr., Garey, M. R., and Johnson, D. S., Dynamic Bin Packing,SIAM J. Comput.,12 (1983), 227–258.
Coffman, E. G., Jr., Garey, M. R., and Johnson, D. S., Approximation Algorithms for Bin Packing-An Updated Survey,Algorithm Design for Computer System Design (G. Ausiello, M. Lucertini, and P. Serafini, eds.), Springer-Verlag, New York, 1984, pp. 49–106.
Coffman, E. G., Jr., Garey, M. R., Johnson, D. S., and Tarjan, R. E., Performance Bounds for Level Oriented Two-Dimensional Packing Algorithms,SIAM J. Comput.,9 (1980), 808–826.
Coffman, E. G., Jr., and Lagarias, J. C., Algorithms for Packing Squares: A Probabilistic Analysis,SIAM J. Comput.,18 (1989), 166–185.
Coffman, E. G., Jr., and Leighton, F. T., A Provably Efficient Algorithm for Dynamic Storage Allocation,J. Comput. System Sci.,38 (1989), 2–35.
Coffman, E. G., Jr., Lueker, G. S., and Rinnooy Kan, A., Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics,Management Sci.,34 (1988), 266–290.
Coffman, E. G., Jr., So, K., Hofri, M., and Yao, A. C., A Stochastic Model of Bin Packing,Inform, and Control,44 (1980), 105–115.
Durbin, J.,Distribution Theory for Tests Based on the Sample Distribution Function, Regional Conference Series in Applied Mathematics, SIAM, Philadelphia, PA, 1973.
Feller, W.,An Introduction to Probability Theory and Its Applications, Vol. I, 3rd edn., Wiley, New York, 1968.
Feller, W.,An Introduction to Probability Theory and Its Applications, Vol. II, 2nd edn., Wiley, New York, 1971.
Halfin, S., Next-Fit Bin Packing with Random Piece Sizes, Technical Report, Bell Communications Research, Morristown, NJ, 1989.
Hoeffding, W., Probability Inequalities for Sums of Bounded Random Variables,Amer. Statist. Assoc. J.,58 (1963), 13–30.
Hoffman, U., A Class of Simple Stochastic On-Line Bin-Packing Algorithms,Computing,29 (1982), 227–239.
Hofri, M., Two-Dimensional Packing: Expected Performance of Simple Level Algorithms,Inform. and Control,45 (1980), 1–17.
Karmarkar, N, Probabilistic Analysis of Some Bin-Packing Algorithms,Proc. 23rd IEEE Sympon. Foundations of Computer Science, 1982, pp. 107–111.
Karp, R. M., Luby, M., and Marchetti-Spaccamela, A., Probabilistic Analysis of Muiti-Dimensional Bin-Packing Problems,Proc. 16th ACM Symp, on Theory of Computing, 1984, pp. 289–298.
Lee, C. C., and Lee, D. T., Robust On-Line Packing Algorithms, Technical Report, Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL, 1989.
Leighton, F. T., and Shor, P. W., Tight Bounds for Minimax Grid Matching, with Applications to the Average-Case Analysis of Algorithms,Combinatorica,9 (1989), 161–187.
Lueker, G. S., An Average-Case Analysis of Bin-Packing with Uniformly Distributed Item Sizes, Technical Report 181, University of California at Irvine, CA, 1982.
Ramanan, P., and Tsuga, K., Average-Case Analysis of the Modified Harmonic Algorithm,Algorithmic,4 (1989), 519–533.
Shor, P. W., The Average-Case Analysis of Some On-Line Algorithms for Bin Packing,Combinatorica,6 (1986), 179–200.
Shor, P. W., How To Do Better than Best Fit: An Improved On-Line Bin Packing Algorithm, AT&T Bell Laboratories, Murray Hill, NJ (to appear).
Talagrand, M., Technical Report, Mathematics Department, Ohio State University, Columbus, OH, 1992.
Author information
Authors and Affiliations
Additional information
Communicated by Franco P. Preparata.
Rights and permissions
About this article
Cite this article
Coffman, E.G., Shor, P.W. Packings in two dimensions: Asymptotic average-case analysis of algorithms. Algorithmica 9, 253–277 (1993). https://doi.org/10.1007/BF01190899
Received:
Revised:
Issue date:
DOI: https://doi.org/10.1007/BF01190899
