Multidimensional Optimal Bin Packing with Items of Random Size

Consider a probability measure μ on [0, 1]^d, and independent random variables X⃗₁, …, X⃗_n distributed according to μ. Let V_n = V_n(X⃗₁, …, X⃗_n) (resp. R_n = R_n(X⃗₁, …, X⃗_n)) be the minimal number of unit size d-dimensional bins needed to pack items of size X⃗₁, …, X⃗_n in the vector packing (resp. rectangular packing) problem. For a large class of distributions μ, we characterize v(μ) = lim_n→∞V_n/n and r(μ) = lim_n→∞R_n/n.