Probabilistic analysis of k-dimensional packing algorithms

In the k-dimensional packing problem, we are given a set I = b₁, b₂,..., 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 the kth dimension. Each box b_i is represented by a k-tupleb_i = (x_i⁽¹⁾,..., x_i^{(k - 1)}, x_i^(k)) ε{lunate} (0, 1]^{k - 1} × (0, ∞), where x^(j) denotes its length in the jth dimension, 1 ≤ j ≤ k. We are asked to find a packing of I into B such that each box is packed orthogonally and oriented in all k dimensions and such that the height in the kth dimension of the packing is minimized. The k-dimensional packing problem is known to be NP-hard for each k < 1. In this note, we study the average-case behavior of a class of algorithms, which includes any optimal algorithm and an on-line algorithm. Let A denote an algorithm in this class. Assume that b₁, b₂,..., b_n are independent, identically distributed according to a distribution F(x⁽¹⁾,..., x^{(k - 1)}, x^(k)) over (0, 1]^{k -1} × (0, ∞), and the marginal distribution F_k of x^(k) satisfies the property that there is a positive number α at which the moment generating function M_Fk(t) has a finite value C_α < 0. It is shown that for each given s < 0, there is an N_s,F < 0 such that for all n ≥ N_s,F, Pr(| A(b₁,...,b_n)/n - Γ | < s) < (2 + C_α)exp(-( sα 3) ^{2 3}n ^{1 3)}, where Γ = lim_{n → ∞}E[A(b₁,..., b_n)] n and A(b₁,..., b_n) denotes the height in the kth dimension of the packing of (b₁,..., b_n) produced by A.