PROBABILISTIC ANALYSIS OF K-DIMENSIONAL PACKING ALGORITHMS

In the k-dimensional packing problem, we are given a set I=(b(1), b(2) ,..., b(n)) of k-dimensional boxes and a k-dimensional box B with unit length in each of the first k-1 dimensions and unbounded length in th e kth dimension. Each box b(i) is represented by a k-tuple b(i) = (x(i )((1)),..., x(i)((k-1)), x(i)((k))) is an element of (0, 1](k-1) X (0, infinity), where x((j)) denotes its length in the jth dimension, 1 le ss than or equal to j less than or equal to k. We are asked to find a packing of I into B such that each box is packed orthogonally and orie nted in all k dimensions and such that the height in the kth dimension of the packing is minimized. The k-dimensional packing problem is kno wn to be NP-hard for each k > 1. In this note, we study the average-ca se behavior of a class of algorithms, which includes any optimal algor ithm and an on-line algorithm. Let A denote an algorithm in this class . Assume that b(1), b(2),..., b(n) are independent, identically distri buted according to a distribution F(x((1)),.., x((k-1)), x((k))) over (0, 1](k-1) X (0, infinity), and the marginal distribution F-k of x((k )) satisfies the property that there is a positive number Lu at which the moment generating function M(Fk)(t) has a finite value C-a > 0. It is shown that for each given s > 0, there is an N-s,N-F > 0 such that for all n greater than or equal to N-s,N-F, Pr(\A(b(1),..., b(n))/n - Gamma\>s) < (2 + C-a)exp(-(sa/3)(2/3)n(1/3)), where Gamma = lim(n-->i nfinity)E[A(b(1),..., b(n))]/n and A(b(1),..., b(n)) denotes the heigh t in the kth dimension of the packing of (b(1),..., b(n)) produced by A.