{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T04:30:13Z","timestamp":1764131413630},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,10,25]],"date-time":"2014-10-25T00:00:00Z","timestamp":1414195200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s00453-014-9943-z","type":"journal-article","created":{"date-parts":[[2014,10,24]],"date-time":"2014-10-24T19:32:58Z","timestamp":1414179178000},"page":"208-269","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["New Approximability Results for Two-Dimensional Bin Packing"],"prefix":"10.1007","volume":"74","author":[{"given":"Klaus","family":"Jansen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lars","family":"Pr\u00e4del","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,10,25]]},"reference":[{"issue":"4","key":"9943_CR1","doi-asserted-by":"crossref","first-page":"1256","DOI":"10.1137\/080736831","volume":"39","author":"N Bansal","year":"2009","unstructured":"Bansal, N., Caprara, A., Sviridenko, M.: A new approximation method for set covering problems, with applications to multidimensional bin packing. SIAM J. Comput. 39(4), 1256\u20131278 (2009)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9943_CR2","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1287\/moor.1050.0168","volume":"31","author":"N Bansal","year":"2006","unstructured":"Bansal, N., Correa, J.R., Kenyon, C., Sviridenko, M.: Bin packing in multiple dimensions: inapproximability results and approximation schemes. Math. Oper. Res. 31(1), 31\u201349 (2006)","journal-title":"Math. Oper. Res."},{"key":"9943_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, N., Khan, A.: Improved approximation algorithm for two-dimensional bin packing. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), pp. 13\u201325 (2014)","DOI":"10.1137\/1.9781611973402.2"},{"issue":"4","key":"9943_CR4","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1142\/S1793830911001413","volume":"3","author":"M Bougeret","year":"2011","unstructured":"Bougeret, M., Dutot, P.-F., Jansen, K., Robenek, C., Trystram, D.: Approximation algorithms for multiple strip packing and scheduling parallel jobs in platforms. Discret. Math. Algorithms Appl. 3(4), 553\u2013586 (2011)","journal-title":"Discret. Math. Algorithms Appl."},{"key":"9943_CR5","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1287\/moor.1070.0289","volume":"33","author":"A Caprara","year":"2008","unstructured":"Caprara, A.: Packing d-dimensional bins in d stages. Math. Oper. Res. 33, 203\u2013215 (2008)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"9943_CR6","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/j.jda.2009.02.002","volume":"7","author":"M Chleb\u00edk","year":"2009","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Hardness of approximation for orthogonal rectangle packing and covering problems. J. Discrete Algorithms 7(3), 291\u2013305 (2009)","journal-title":"J. Discrete Algorithms"},{"key":"9943_CR7","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1137\/0603007","volume":"3","author":"FRK Chung","year":"1982","unstructured":"Chung, F.R.K., Garey, M.R., Johnson, D.S.: On packing two-dimensional bins. SIAM J. Algebr. Discret. Methods 3, 66\u201376 (1982)","journal-title":"SIAM J. Algebr. Discret. Methods"},{"issue":"4","key":"9943_CR8","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1137\/0209062","volume":"9","author":"EG 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 J. Comput. 9(4), 808\u2013826 (1980)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"9943_CR9","first-page":"1277","volume":"11","author":"EA Dinic","year":"1970","unstructured":"Dinic, E.A.: An algorithm for solution of a problem of maximum flow in a network with power estimation. Sov. Math. Dokl. 11(5), 1277\u20131280 (1970)","journal-title":"Sov. Math. Dokl."},{"issue":"5","key":"9943_CR10","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1016\/j.orl.2005.09.008","volume":"34","author":"F Eisenbrand","year":"2006","unstructured":"Eisenbrand, F., Shmonin, G.: Carath\u00e9odory bounds for integer cones. Oper. Res. Lett. 34(5), 564\u2013568 (2006)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"9943_CR11","doi-asserted-by":"crossref","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 + \\epsilon $$ 1 + \u03f5 in linear time. Combinatorica 1(4), 349\u2013355 (1981)","journal-title":"Combinatorica"},{"issue":"4","key":"9943_CR12","doi-asserted-by":"crossref","first-page":"1081","DOI":"10.1137\/S1052623499358689","volume":"11","author":"MD Grigoriadis","year":"2001","unstructured":"Grigoriadis, M.D., Khachiyan, L.G., Porkolab, L., Villavicencio, J.: Approximate max\u2013min resource sharing for structured concave optimization. SIAM J. Optim. 11(4), 1081\u20131091 (2001)","journal-title":"SIAM J. Optim."},{"key":"9943_CR13","doi-asserted-by":"crossref","unstructured":"Harren, R., van Stee, R.: Absolute approximation ratios for packing rectangles into bins. J. Sched. 15(1), 63\u201375 (2012)","DOI":"10.1007\/s10951-009-0110-3"},{"key":"9943_CR14","doi-asserted-by":"crossref","unstructured":"Harren, R., van Stee, R.: Improved absolute approximation ratios for two-dimensional packing problems. In: Proceedings of the 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2009), LNCS 5687, pp. 177\u2013189 (2009)","DOI":"10.1007\/978-3-642-03685-9_14"},{"key":"9943_CR15","doi-asserted-by":"crossref","unstructured":"Jansen, K.: Efficient Approximation and Online Algorithms, chapter Approximation Algorithms for min\u2013max and max\u2013min Resource Sharing Problems and Applications, LNCS 3484, pp. 156\u2013202. Springer, Berlin (2006)","DOI":"10.1007\/11671541_6"},{"key":"9943_CR16","doi-asserted-by":"crossref","unstructured":"Jansen, K., Pr\u00e4del, L.: A new asymptotic approximation algorithm for 3-dimensional strip packing. In: Theory and Practice of Computer Science\u201440th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2014), LNCS 8327, pp. 327\u2013338 (2014)","DOI":"10.1007\/978-3-319-04298-5_29"},{"key":"9943_CR17","doi-asserted-by":"crossref","unstructured":"Jansen, K., Pr\u00e4del, L., Schwarz, U. M.: Two for one: Tight approximation of 2d bin packing. In: Proceedings of the 11th International Symposium on Algorithms and Data Structures (WADS 2009), LNCS 5664, pp. 399\u2013410 (2009)","DOI":"10.1007\/978-3-642-03367-4_35"},{"issue":"3","key":"9943_CR18","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1016\/j.disopt.2009.04.001","volume":"6","author":"K Jansen","year":"2009","unstructured":"Jansen, K., Solis-Oba, R.: Rectangle packing with one-dimensional resource augmentation. Discret. Optim. 6(3), 310\u2013323 (2009)","journal-title":"Discret. Optim."},{"key":"9943_CR19","doi-asserted-by":"crossref","unstructured":"Jansen, K., van Stee, R.: On strip packing with rotations. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing (STOC 2005), pp. 755\u2013761 (2005)","DOI":"10.1145\/1060590.1060702"},{"issue":"3","key":"9943_CR20","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan, R.: Minkowski\u2019s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415\u2013440 (1987)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"9943_CR21","doi-asserted-by":"crossref","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. Math. Oper. Res. 25(4), 645\u2013656 (2000)","journal-title":"Math. Oper. Res."},{"key":"9943_CR22","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1287\/moor.4.4.339","volume":"4","author":"EL Lawler","year":"1979","unstructured":"Lawler, E.L.: Fast approximation algorithms for knapsack problems. Math. Oper. Res. 4, 339\u2013356 (1979)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"9943_CR23","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0743-7315(90)90019-L","volume":"10","author":"JY-T Leung","year":"1990","unstructured":"Leung, J.Y.-T., Tam, T.W., Wong, C.S., Young, G.H., Chin, F.Y.L.: Packing squares into a square. J. Parallel Distrib. Comput. 10(3), 271\u2013275 (1990)","journal-title":"J. Parallel Distrib. Comput."},{"issue":"2","key":"9943_CR24","doi-asserted-by":"crossref","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 J. Comput. 26(2), 401\u2013409 (1997)","journal-title":"SIAM J. Comput."},{"key":"9943_CR25","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF01580859","volume":"47","author":"PM Vaidya","year":"1990","unstructured":"Vaidya, P.M.: An algorithm for linear programming which requires $${\\cal O}(((m+n)n^{2} + (m+n)^{1.5}n) L )$$ O ( ( ( m + n ) n 2 + ( m + n ) 1.5 n ) L ) arithmetic operations. Math. Program. 47, 175\u2013201 (1990)","journal-title":"Math. Program."},{"issue":"2","key":"9943_CR26","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/j.orl.2004.04.004","volume":"33","author":"G Zhang","year":"2005","unstructured":"Zhang, G.: A 3-approximation algorithm for two-dimensional bin packing. Oper. Res. Lett. 33(2), 121\u2013126 (2005)","journal-title":"Oper. Res. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9943-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9943-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9943-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T16:22:41Z","timestamp":1565972561000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9943-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,25]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9943"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9943-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,25]]}}}