Hardness of approximation for orthogonal rectangle packing and covering problems

Ausiello, 1999 Baker, 1983, Approximation algorithms for maximizing the number of squares packed into a rectangle, SIAM Journal on Algebraic and Discrete Methods, 4, 383, 10.1137/0604039 Bansal, 2006, Bin packing in multiple dimensions: Inapproximability results and approximation schemes, Mathematics of Operations Research, 31, 31, 10.1287/moor.1050.0168 N. Bansal, M. Sviridenko, New approximability and inapproximability results for 2-dimensional bin packing, in: Proceedings of the 15th Annual ACM–SIAM Symposium on Discrete Algorithms, SODA, 2004, pp. 189–196 A. Caprara, Packing 2-dimensional bins in harmony, in: Proceedings of the 43th Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2002, pp. 490–499 C. Chekuri, S. Khanna, On multi-dimensional packing problems, in: Proc. of the 10th ACM–SIAM Symposium on Discrete Algorithms, SODA, 1999, pp. 185–194 Chlebík, 2006, Complexity of approximating bounded variants of optimization problems, Theoretical Computer Science, 354, 320, 10.1016/j.tcs.2005.11.029 J.R. Correa, C. Kenyon, Approximation schemes for multidimensional packing, in: Proceedings of the 15th ACM–SIAM Symposium on Discrete Algorithms, SODA, 2004, pp. 179–188 J. Csirik, D.S. Johnson, C. Kenyon, Better approximation algorithms for bin covering, in: Proceedings of the 12th ACM–SIAM Symposium on Discrete Algorithms, SODA (2001), 557–566 Csirik, 1993, An on-line algorithm for multidimensional bin packing, Operation Research Letters, 13, 149, 10.1016/0167-6377(93)90004-Z Fernandez de la Vega, 1981, Bin packing can be solved within (1+ε) in linear time, Combinatorica, 1, 349, 10.1007/BF02579456 A. Freund, J. Naor, Approximating the advertisement placement problem, in: Proceedings of the 9th Conference on Integer Programming and Combinatorial Optimization, IPCO, in: LNCS, vol. 2337, 2002, pp. 415–424 Jansen, 2003, An asymptotic fully polynomial time approximation scheme for bin covering, Theoretical Computer Science, 306, 543, 10.1016/S0304-3975(03)00363-3 K. Jansen, R. Solis-Oba, An asymptotic approximation algorithm for 3d-strip packing, in: Proceedings of the 17th Annual ACM–SIAM Symposium on Discrete Algorithms, SODA, 2006, pp. 143–152 K. Jansen, R. Stee, On strip packing with rotations, in: Proceedings of the 37th ACM Symposium on Theory of Computing, STOC, 2005, pp. 755–761 K. Jansen, G. Zhang, On rectangle packing: Maximizing benefits, in: Proceedings of the 15th Annual ACM–SIAM Symposium on Discrete Algorithms, SODA, 2004, pp. 197–206 Kann, 1991, Maximum bounded 3-dimensional matching is MAX SNP complete, Information Processing Letters, 37, 27, 10.1016/0020-0190(91)90246-E N. Karmarkar, R.M. Karp, An efficient approximation scheme for the one-dimensional bin-packing problem, in: Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, FOCS, 1982, pp. 312–320 Kenyon, 2000, A near optimal solution to a two-dimensional cutting stock problem, Mathematics of Operations Research, 25, 645, 10.1287/moor.25.4.645.12118 Li, 1990, On three-dimensional packing, SIAM J. Comput., 19, 847, 10.1137/0219059 Miyazawa, 2000, Approximation algorithms for the orthogonal z-oriented three-dimensional packing problems, SIAM J. Comput., 29, 1008, 10.1137/S009753979631391X Miyazawa, 2004, Packing problems with orthogonal rotations, vol. 2976, 359 Petrank, 1994, The hardness of approximation: Gap location, Computational Complexity, 4, 133, 10.1007/BF01202286 Woeginger, 1997, There is no asymptotic PTAS for two-dimensional vector packing, Information Processing Letters, 64, 293, 10.1016/S0020-0190(97)00179-8