{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T03:52:14Z","timestamp":1794369134387,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642106309","type":"print"},{"value":"9783642106316","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-10631-6_10","type":"book-chapter","created":{"date-parts":[[2009,12,4]],"date-time":"2009-12-04T02:03:43Z","timestamp":1259892223000},"page":"77-86","source":"Crossref","is-referenced-by-count":15,"title":["A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability"],"prefix":"10.1007","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alberto","family":"Caprara","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Klaus","family":"Jansen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lars","family":"Pr\u00e4del","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maxim","family":"Sviridenko","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1137\/0209064","volume":"9","author":"B.S. Baker","year":"1980","unstructured":"Baker, B.S., Coffman Jr., E.G., Rivest, R.L.: Orthogonal packing in two dimensions. SIAM Journal on Computing\u00a09, 846\u2013855 (1980)","journal-title":"SIAM Journal on Computing"},{"key":"10_CR2","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1137\/0212033","volume":"12","author":"B.S. Baker","year":"1983","unstructured":"Baker, B.S., Schwartz, J.S.: Shelf algorithms for two-dimensional packing problems. SIAM Journal on Computing\u00a012, 508\u2013525 (1983)","journal-title":"SIAM Journal on Computing"},{"key":"10_CR3","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1287\/moor.1050.0168","volume":"31","author":"N. Bansal","year":"2006","unstructured":"Bansal, N., Correa, J., Kenyon, C., Sviridenko, M.: Bin packing in multiple dimensions: inapproximability results and approximation schemes. Mathematics of Operations Research\u00a031, 31\u201349 (2006)","journal-title":"Mathematics of Operations Research"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Bansal, N., Caprara, A., Sviridenko, M.: Improved approximation algorithms for multidimensional bin packing problems. In: Proceedings of the 47-th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 697\u2013708 (2006)","DOI":"10.1109\/FOCS.2006.38"},{"key":"10_CR5","unstructured":"Bansal, N., Caprara, A., Sviridenko, M.: A New Approximation Method for Set Covering Problems with Applications to Multidimensional Bin Packing. In: SICOMP (to appear)"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"Bansal, N., Lodi, A., Sviridenko, M.: A tale of two dimensional bin packing. In: Proceedings of the 46-th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), pp. 657\u2013666 (2005)","DOI":"10.1109\/SFCS.2005.10"},{"key":"10_CR7","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.disopt.2006.09.001","volume":"4","author":"N. Bansal","year":"2007","unstructured":"Bansal, N., Sviridenko, M.: Two-dimensional bin packing with one dimensional resource augmentation. Discrete Optimization\u00a04, 143\u2013153 (2007)","journal-title":"Discrete Optimization"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Caprara, A.: Packing 2-dimensional bins in harmony. In: Proceedings of the 43-rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2002), pp. 490\u2013499 (2002)","DOI":"10.1109\/SFCS.2002.1181973"},{"key":"10_CR9","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1287\/moor.1040.0112","volume":"30","author":"A. Caprara","year":"2005","unstructured":"Caprara, A., Lodi, A., Monaci, M.: Fast approximation schemes for two-stage, two-dimensional bin packing. Mathematics of Operations Research\u00a030, 150\u2013172 (2005)","journal-title":"Mathematics of Operations Research"},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/S0167-6377(03)00057-9","volume":"32","author":"A. Caprara","year":"2004","unstructured":"Caprara, A., Monaci, M.: On the 2-dimensional knapsack problem. Operations Research Letters\u00a032, 5\u201314 (2004)","journal-title":"Operations Research Letters"},{"key":"10_CR11","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s10107-007-0184-7","volume":"118","author":"A. Caprara","year":"2009","unstructured":"Caprara, A., Monaci, M.: Bidimensional packing by bilinear programming. Mathematical Programming\u00a0118, 75\u2013108 (2009)","journal-title":"Mathematical Programming"},{"key":"10_CR12","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1137\/0603007","volume":"3","author":"F.R.K. Chung","year":"1982","unstructured":"Chung, F.R.K., Garey, M.R., Johnson, D.S.: On packing two-dimensional bins. SIAM Journal on Algebraic and Discrete Methods\u00a03, 66\u201376 (1982)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"10_CR13","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1137\/0209062","volume":"9","author":"E.G. Coffman Jr.","year":"1980","unstructured":"Coffman Jr., E.G., Garey, M.R., Johnson, D.S., Tarjan, R.E.: Performance bounds for level-oriented two-dimensional packing algorithms. SIAM Journal on Computing\u00a09, 808\u2013826 (1980)","journal-title":"SIAM Journal on Computing"},{"key":"10_CR14","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.orl.2005.02.005","volume":"34","author":"J.R. Correa","year":"2006","unstructured":"Correa, J.R.: Resource augmentation in two-dimensional packing with orthogonal rotations. Operations Research Letters\u00a034, 85\u201393 (2006)","journal-title":"Operations Research Letters"},{"key":"10_CR15","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":"10_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1007\/11602613_103","volume-title":"Algorithms and Computation","author":"A.V. Fishkin","year":"2005","unstructured":"Fishkin, A.V., Gerber, O., Jansen, K.: On efficient weighted rectangle packing with large resources. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 1039\u20131050. Springer, Heidelberg (2005)"},{"key":"10_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1007\/11549345_31","volume-title":"Mathematical Foundations of Computer Science 2005","author":"A.V. Fishkin","year":"2005","unstructured":"Fishkin, A.V., Gerber, O., Jansen, K., Solis-Oba, R.: Packing weighted rectangles into a square. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol.\u00a03618, pp. 352\u2013363. Springer, Heidelberg (2005)"},{"key":"10_CR18","doi-asserted-by":"publisher","first-page":"1081","DOI":"10.1137\/S1052623499358689","volume":"11","author":"M.D. Grigoriadis","year":"2001","unstructured":"Grigoriadis, M.D., Khachiyan, L.G., Porkolab, L., Villavicencio, J.: Approximate max-min resource sharing for structured concave optimization. SIAM Journal on Optimization\u00a011, 1081\u20131091 (2001)","journal-title":"SIAM Journal on Optimization"},{"key":"10_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric algorithms and combinatorial optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lovsz, L., Schrijver, A.: Geometric algorithms and combinatorial optimization. Springer, Berlin (1988)"},{"key":"10_CR20","doi-asserted-by":"crossref","unstructured":"Harren, R., van Stee, R.: Improved absolute approximation ratios for two-dimensional packing problems. In: Naor, S. (ed.) APPROX 2009, pp. 177\u2013189 (2009)","DOI":"10.1007\/978-3-642-03685-9_14"},{"key":"10_CR21","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O.H. Ibarra","year":"1975","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and subset sum problems. Journal of the ACM\u00a022, 463\u2013468 (1975)","journal-title":"Journal of the ACM"},{"key":"10_CR22","unstructured":"Jansen, K., Pr\u00e4del, L.: An Approximation Algorithm for Two-Dimensional Strip-Packing with Absolute Performance Bound \n                  \n                    \n                  \n                  ${\\frac{7}{4}+\\varepsilon}$\n                . Unpublished Manuscript"},{"key":"10_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/978-3-642-03367-4_35","volume-title":"WADS 2009","author":"K. Jansen","year":"2009","unstructured":"Jansen, K., Pr\u00e4del, L., Schwarz, U.M.: A 2-approximation for 2D Bin Packing. In: WADS 2009. LNCS, vol.\u00a05664, pp. 399\u2013410. Springer, Heidelberg (2009)"},{"key":"10_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/978-3-540-74456-6_11","volume-title":"Mathematical Foundations of Computer Science 2007","author":"K. Jansen","year":"2007","unstructured":"Jansen, K., Solis-Oba, R.: New approximability results for 2-dimensional packing problems. In: Ku\u010dera, L., Ku\u010dera, A. (eds.) MFCS 2007. LNCS, vol.\u00a04708, pp. 103\u2013114. Springer, Heidelberg (2007)"},{"key":"10_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/978-3-540-68891-4_13","volume-title":"Integer Programming and Combinatorial Optimization","author":"K. Jansen","year":"2008","unstructured":"Jansen, K., Solis-Oba, R.: A polynomial time approximation scheme for the square packing problem. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol.\u00a05035, pp. 184\u2013198. Springer, Heidelberg (2008)"},{"key":"10_CR26","doi-asserted-by":"crossref","unstructured":"Jansen, K., van Stee, R.: On strip packing with rotations. In: Proceedings of the 37-th Annual ACM Symposium on the Theory of Computing (STOC 2005), pp. 755\u2013761 (2005)","DOI":"10.1145\/1060590.1060702"},{"key":"10_CR27","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/s00453-006-0194-5","volume":"47","author":"K. Jansen","year":"2007","unstructured":"Jansen, K., Zhang, G.: Maximizing the total profit of rectangles packed into a rectangle. Algorithmica\u00a047, 323\u2013342 (2007)","journal-title":"Algorithmica"},{"key":"10_CR28","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1287\/moor.25.4.645.12118","volume":"25","author":"C. Kenyon","year":"2000","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)","journal-title":"Mathematics of Operations Research"},{"key":"10_CR29","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 Annual IEEE Symposium on Foundations of Computer Science (FOCS 1982), pp. 312\u2013320 (1982)","DOI":"10.1109\/SFCS.1982.61"},{"key":"10_CR30","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1145\/3828.3833","volume":"32","author":"C.C. Lee","year":"1985","unstructured":"Lee, C.C., Lee, D.T.: A simple on-line bin packing algorithm. Journal of the ACM\u00a032, 562\u2013572 (1985)","journal-title":"Journal of the ACM"},{"key":"10_CR31","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"S.A. Plotkin","year":"1995","unstructured":"Plotkin, S.A., Shmoys, D., Tardos, E.: Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research\u00a020, 257\u2013301 (1995)","journal-title":"Mathematics of Operations Research"},{"key":"10_CR32","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1145\/321864.321873","volume":"22","author":"S. Sahni","year":"1975","unstructured":"Sahni, S.: Approximate algorithms for the 0\/1 knapsack problem. Journal of the ACM\u00a022, 115\u2013124 (1975)","journal-title":"Journal of the ACM"},{"key":"10_CR33","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1137\/S0097539793255801","volume":"26","author":"A. Steinberg","year":"1997","unstructured":"Steinberg, A.: A strip-packing algorithm with absolute performance bound 2. SIAM Journal on Computing\u00a026, 401\u2013409 (1997)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-10631-6_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T07:36:40Z","timestamp":1619768200000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-10631-6_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642106309","9783642106316"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-10631-6_10","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-642-10631-6","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}