Polynomial Approximation Schemes for Smoothed And Random Instances of Multidimensional Packing Problems

Abstract: The multidimensional bin packing and vector bin packing problems are known to not have asymptotic polynomial-time approximation schemes (unless $\mbox{P} = \mbox{NP}$). Nevertheless, we show that:

• Any smoothed (randomly perturbed) instance, and any instance from a class of other distributions, does have a polynomial-time probable approximation scheme. Namely, for any fixed $\epsilon > 0$, we exhibit a linear-time algorithm that finds a $(1+\epsilon)$-approximate packing with probability $1 - 2^{-\Omega(n)}$ over the space of random inputs.
• There exists an oblivious algorithm that does not know from which distribution inputs come, and still asymptotically does almost as well as the previous algorithms. The oblivious algorithm outputs almost surely a $(1+\epsilon)$-approximation for every $\epsilon > 0$.
• For vector bin packing, for each considered class of random instances, there exists an algorithm that in expected linear time computes a $(1+\epsilon)$-approximation, for any fixed $\epsilon > 0$.

To achieve these results we develop a multidimensional version of the one-dimensional rounding technique introduced by Fernadez de la Vega and Lueker. Our results generalize Karp, Luby and Marchetti-Spaccamela's results on approximatibility of random instances of multidimensional bin packing to a much wider class of distributions.