Inapproximability Results for Orthogonal Rectangle Packing Problems with Rotations

1. Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and approximation. Springer, Heidelberg (1999)

   MATH  Google Scholar 

2. Baker, B.S., Calderbank, A.R., Coffman, E.G., Lagarias, J.C.: Approximation algorithms for maximizing the number of squares packed into a rectangle. SIAM J. on Algebraic and Discrete Methods 4, 383–397 (1983)

   Article  MATH  MathSciNet  Google Scholar 

3. Bansal, N., Correa, J.R., Kenyon, C., Sviridenko, M.: Bin packing in multiple dimensions: inapproximability results and approximation schemes (February 2004) (manuscript)

   Google Scholar 

4. Bansal, N., Sviridenko, M.: New approximability and inapproximability results for 2-dimensional bin packing. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 189–196 (2004)

   Google Scholar 

5. Caprara, A.: Packing 2-dimensional bins in harmony. In: Proceedings of the 43th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 490–499 (2002)

   Google Scholar 

6. Chekuri, C., Khanna, S.: On multi-dimensional packing problems. In: Proc. of the 10th ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 185–194 (1999)

   Google Scholar 

7. Chlebík, M., Chlebíková, J.: Complexity of approximating bounded variants of optimization problems. Theoretical Computer Science 354, 320–338 (2006)

   Article  MATH  MathSciNet  Google Scholar 

8. Correa, J.R., Kenyon, C.: Approximation schemes for multidimensional packing. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 179–188 (2004)

   Google Scholar 

9. Csirik, J., van Vliet, A.: An on-line algorithm for multidimensional bin packing. Operation Research Letters 13, 149–158 (1993)

   Article  MATH  Google Scholar 

10. Fernandez de la Vega, W., Lueker, G.S.: Bin packing can be solved within (1 + ε) in linear time. Combinatorica 1, 349–355 (1981)

    Article  MATH  MathSciNet  Google Scholar 

11. Jansen, K., Solis-Oba, R.: An asymptotic approximation algorithm for 3d-strip packing. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2006)

    Google Scholar 

12. Jansen, K., Stee, R.: On strip packing with rotations. In: Proceedings of the 37th ACM Symposium on Theory of Computing, STOC, pp. 755–761 (2005)

    Google Scholar 

13. Jansen, K., Zhang, G.: On rectangle packing: maximizing benefits. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 197–206 (2004)

    Google Scholar 

14. Kann, V.: Maximum bounded 3-dimensional matching is MAX SNP complete. Information Processing Letters 37, 27–35 (1991)

    Article  MATH  MathSciNet  Google Scholar 

15. Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, FOCS, pp. 312–320 (1982)

    Google Scholar 

16. Kenyon, C., Rémila, E.: A near optimal solution to a two-dimensional cutting stock problem. Mathematics of Operations Research 25, 645–656 (2000); Preliminary version in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 31–36 (1996)

    Google Scholar 

17. Li, K., Cheng, K.H.: On three-dimensional packing. SIAM J. Comput. 19, 847–867 (1990)

    Article  MATH  MathSciNet  Google Scholar 

18. Miyazawa, F.K., Wakabayashi, Y.: Approximation algorithms for the orthogonal z-oriented three-dimensional packing problems. SIAM J. Comput. 29, 1008–1029 (2000)

    Article  MATH  MathSciNet  Google Scholar 

19. Miyazawa, F.K., Wakabayashi, Y.: Packing problems with orthogonal rotations. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol. 2976, pp. 359–368. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

20. Petrank, E.: The hardness of approximation: Gap location. Computational Complexity 4, 133–157 (1994)

    Article  MATH  MathSciNet  Google Scholar 

21. Woeginger, G.J.: There is no asymptotic PTAS for two-dimensional vector packing. Information Processing Letters 64(6), 293–297 (1997)

    Article  MathSciNet  Google Scholar 

Download references