{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T05:06:53Z","timestamp":1736485613767,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540343752"},{"type":"electronic","value":"9783540343783"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11758471_21","type":"book-chapter","created":{"date-parts":[[2006,6,2]],"date-time":"2006-06-02T10:34:15Z","timestamp":1149244455000},"page":"199-210","source":"Crossref","is-referenced-by-count":8,"title":["Inapproximability Results for Orthogonal Rectangle Packing Problems with Rotations"],"prefix":"10.1007","author":[{"given":"Miroslav","family":"Chleb\u00edk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Janka","family":"Chleb\u00edkov\u00e1","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and approximation","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and approximation. Springer, Heidelberg (1999)"},{"key":"21_CR2","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1137\/0604039","volume":"4","author":"B.S. Baker","year":"1983","unstructured":"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\u00a04, 383\u2013397 (1983)","journal-title":"SIAM J. on Algebraic and Discrete Methods"},{"key":"21_CR3","unstructured":"Bansal, N., Correa, J.R., Kenyon, C., Sviridenko, M.: Bin packing in multiple dimensions: inapproximability results and approximation schemes (February 2004) (manuscript)"},{"key":"21_CR4","unstructured":"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\u2013196 (2004)"},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"Caprara, A.: Packing 2-dimensional bins in harmony. In: Proceedings of the 43th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 490\u2013499 (2002)","DOI":"10.1109\/SFCS.2002.1181973"},{"key":"21_CR6","unstructured":"Chekuri, C., Khanna, S.: On multi-dimensional packing problems. In: Proc. of the 10th ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 185\u2013194 (1999)"},{"key":"21_CR7","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1016\/j.tcs.2005.11.029","volume":"354","author":"M. Chleb\u00edk","year":"2006","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Complexity of approximating bounded variants of optimization problems. Theoretical Computer Science\u00a0354, 320\u2013338 (2006)","journal-title":"Theoretical Computer Science"},{"key":"21_CR8","unstructured":"Correa, J.R., Kenyon, C.: Approximation schemes for multidimensional packing. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 179\u2013188 (2004)"},{"key":"21_CR9","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0167-6377(93)90004-Z","volume":"13","author":"J. Csirik","year":"1993","unstructured":"Csirik, J., van Vliet, A.: An on-line algorithm for multidimensional bin packing. Operation Research Letters\u00a013, 149\u2013158 (1993)","journal-title":"Operation Research Letters"},{"key":"21_CR10","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W. Fernandez de la Vega","year":"1981","unstructured":"Fernandez de la Vega, W., Lueker, G.S.: Bin packing can be solved within (1\u2009+\u2009\u03b5) in linear time. Combinatorica\u00a01, 349\u2013355 (1981)","journal-title":"Combinatorica"},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"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)","DOI":"10.1145\/1109557.1109575"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Jansen, K., Stee, R.: On strip packing with rotations. In: Proceedings of the 37th ACM Symposium on Theory of Computing, STOC, pp. 755\u2013761 (2005)","DOI":"10.1145\/1060590.1060702"},{"key":"21_CR13","unstructured":"Jansen, K., Zhang, G.: On rectangle packing: maximizing benefits. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 197\u2013206 (2004)"},{"key":"21_CR14","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0020-0190(91)90246-E","volume":"37","author":"V. Kann","year":"1991","unstructured":"Kann, V.: Maximum bounded 3-dimensional matching is MAX SNP complete. Information Processing Letters\u00a037, 27\u201335 (1991)","journal-title":"Information Processing Letters"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"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\u2013320 (1982)","DOI":"10.1109\/SFCS.1982.61"},{"key":"#cr-split#-21_CR16.1","doi-asserted-by":"crossref","unstructured":"Kenyon, C., R\u00e9mila, E.: A near optimal solution to a two-dimensional cutting stock problem. Mathematics of Operations Research\u00a025, 645\u2013656 (2000);","DOI":"10.1287\/moor.25.4.645.12118"},{"key":"#cr-split#-21_CR16.2","unstructured":"Preliminary version in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 31\u201336 (1996)"},{"key":"21_CR17","doi-asserted-by":"publisher","first-page":"847","DOI":"10.1137\/0219059","volume":"19","author":"K. Li","year":"1990","unstructured":"Li, K., Cheng, K.H.: On three-dimensional packing. SIAM J. Comput.\u00a019, 847\u2013867 (1990)","journal-title":"SIAM J. Comput."},{"key":"21_CR18","doi-asserted-by":"publisher","first-page":"1008","DOI":"10.1137\/S009753979631391X","volume":"29","author":"F.K. Miyazawa","year":"2000","unstructured":"Miyazawa, F.K., Wakabayashi, Y.: Approximation algorithms for the orthogonal z-oriented three-dimensional packing problems. SIAM J. Comput.\u00a029, 1008\u20131029 (2000)","journal-title":"SIAM J. Comput."},{"key":"21_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/978-3-540-24698-5_40","volume-title":"LATIN 2004: Theoretical Informatics","author":"F.K. Miyazawa","year":"2004","unstructured":"Miyazawa, F.K., Wakabayashi, Y.: Packing problems with orthogonal rotations. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol.\u00a02976, pp. 359\u2013368. Springer, Heidelberg (2004)"},{"key":"21_CR20","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01202286","volume":"4","author":"E. Petrank","year":"1994","unstructured":"Petrank, E.: The hardness of approximation: Gap location. Computational Complexity\u00a04, 133\u2013157 (1994)","journal-title":"Computational Complexity"},{"issue":"6","key":"21_CR21","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/S0020-0190(97)00179-8","volume":"64","author":"G.J. Woeginger","year":"1997","unstructured":"Woeginger, G.J.: There is no asymptotic PTAS for two-dimensional vector packing. Information Processing Letters\u00a064(6), 293\u2013297 (1997)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11758471_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T05:17:14Z","timestamp":1736399834000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11758471_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540343752","9783540343783"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11758471_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}