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 P = 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 ε > 0, we exhibit a linear-time algorithm that finds a (1+ ε)-approximate packing with probability 1 - 2^-Ω(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 + ε)-approximation for every ε > 0.

• For vector bin packing, for each considered class of random instances, there exists an algorithm that in expected linear time computes a (1 + ε)-approximation, for any fixed ε > 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.

REFERENCES

• 1: Nikhil Bansal , Alberto Caprara , Maxim Sviridenko, Improved approximation algorithms for multidimensional bin packing problems, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.697-708, October 21-24, 2006 [doi>10.1109/FOCS.2006.38]
• 2: Nikhil Bansal , Jos R. Correa , Claire Kenyon , Maxim Sviridenko, Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes, Mathematics of Operations Research, v.31 n.1, p.31-49, February 2006 [doi>10.1287/moor.1050.0168]
• 3: Alberto Caprara, Packing 2-Dimensional Bins in Harmony, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.490-499, November 16-19, 2002
• 4: Chandra Chekuri , Sanjeev Khanna, On Multidimensional Packing Problems, SIAM Journal on Computing, v.33 n.4, p.837-851, 2004 [doi>10.1137/S0097539799356265]
• 5: E. G. Coffman, Jr. , M. R. Garey , D. S. Johnson, Approximation algorithms for bin packing: a survey, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 6: M. E. Dyer , A. M. Frieze, The solution of some random NP-hard problems in polynomial expected time, Journal of Algorithms, v.10 n.4, p.451-489, Dec. 1989 [doi>10.1016/0196-6774(89)90001-1]
• 7: W. Fernandez de la Vega and G. Lueker. Bin packing can be solved within 1 + ε in linear time. Combinatorica, 1:349--355, 1981.
• 8: Ravi Kannan, Minkowski's convex body theorem and integer programming, Mathematics of Operations Research, v.12 n.3, p.415-440, August 1, 1987 [doi>10.1287/moor.12.3.415]
• 9: N. Karmarkar and R. M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In Proceedings of the 23th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1982), pages 312--320, 1982.
• 10: Richard M. Karp , Michael Luby , A. Marchetti-Spaccamela, A probabilistic analysis of multidimensional bin packing problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.289-298, December 1984 [doi>10.1145/800057.808693]
• 11: H. Lenstra. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8:538--548, 1983.
• 12: Daniel A. Spielman , Shang-Hua Teng, Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, Journal of the ACM (JACM), v.51 n.3, p.385-463, May 2004 [doi>10.1145/990308.990310]
• 13: Gerhard J. Woeginger, There is no asymptotic PTAS for two-dimensional vector packing, Information Processing Letters, v.64 n.6, p.293-297, Dec. 29, 1997 [doi>10.1016/S0020-0190(97)00179-8]