Algorithms for Packing Squares: A Probabilistic Analysis
Authors:
- 1 February 1989
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 18 (1) , 166-185
Abstract
This paper gives a probabilistic performance analysis of simple algorithms for packing lists $L_n $, of n squares into a strip or a set of bins. It is assumed that the square sizes are drawn independently from the uniform distribution on,$[0,1]$. The strip-packing problem is to pack the squares into a strip of width 1 so as to minimize the height of the packing. Let ${\operatorname{OPT}}(L_n)$ denote the height of an optimal strip packing for list $L_n $. A simple $O(n\log n)$ approximation algorithm, called Algorithm A, is described and it is proven that the height $A(L_n )$ of a packing of list $L_n $ satisfies $A(L_n ) - {\operatorname{OPT}}(L_n ) \leqq \tfrac{1}{4}$ with probability $1 - O(e^{ - c_0 n} )$ for a positive constant $c_0 $. It is also shown that $E[{\operatorname{OPT}}(L_n )] = 3n/8 + \Theta (n^{{1 / 3}} )$. The bin-packing problem is to pack the squares into square bins of size 1 so as to minimize the number of bins. Let ${\operatorname{OPT}}_B (L_n )$ denote the number of bins in an optimal packing of list $L_n $. The authors present another $O(n\log n)$ approximation algorithm and show that the number of bins it needs to pack a list $L_n $ is precisely ${\operatorname{OPT}}_B (L_n )$ with probability $1 - O(e^{ - c_1 n} )$ for a positive constant $c_1 $. Finally, it is shown that $E[{\operatorname{OPT}}_B (L_n )] = {n / 2} + \Theta (1)$. These bounds for packing squares into strips and bins are much tighter than GTthose that have been obtained for packing rectangles.
Keywords
This publication has 5 references indexed in Scilit:
- Approximation Algorithms for Bin-Packing — An Updated Survey1984
- A probabilistic analysis of multidimensional bin packing problems1984
- Approximation Algorithms for Maximizing the Number of Squares Packed into a RectangleSIAM Journal on Algebraic Discrete Methods, 1983
- Two-dimensional packing: expected performance of simple level algorithmsInformation and Control, 1980
- Probability Inequalities for the Sum of Independent Random VariablesJournal of the American Statistical Association, 1962