{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,4]],"date-time":"2024-07-04T00:34:19Z","timestamp":1720053259277},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,9,2]],"date-time":"2015-09-02T00:00:00Z","timestamp":1441152000000},"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":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,8]]},"DOI":"10.1007\/s00224-015-9644-2","type":"journal-article","created":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T00:51:29Z","timestamp":1441068689000},"page":"262-322","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["An Improved Approximation Scheme for Variable-Sized Bin Packing"],"prefix":"10.1007","volume":"59","author":[{"given":"Klaus","family":"Jansen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Kraft","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,9,2]]},"reference":[{"issue":"1\u20132","key":"9644_CR1","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/S0304-3975(98)00003-6","volume":"205","author":"PA Beling","year":"1998","unstructured":"Beling, P.A., Megiddo, N.: Using fast matrix multiplication to find basic solutions. Theor. Comput. Sci. 205(1\u20132), 307\u2013316 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"9644_CR2","volume-title":"Dynamic programming","author":"RE Bellman","year":"1957","unstructured":"Bellman, R.E.: Dynamic programming. Princeton University Press, Princeton (1957)"},{"key":"9644_CR3","unstructured":"Diedrich, F.: Approximation algorithms for linear programs and geometrically constrained packing problems, Ph.D. thesis. Christian-Albrechts-Universit\u00e4t zu Kiel (2009)"},{"key":"9644_CR4","doi-asserted-by":"crossref","unstructured":"D\u00f3sa, G.: The tight bound of first fit decreasing bin-packing algorithm is FFD ( I ) \u2264 11 9 OPT ( I ) + 6 9 $FFD(I) \\leq \\frac {11}{9}OPT(I) + \\frac {6}{9}$ . In: Chen, B., Paterson, M., Zhang, G. (eds.) Proceedings of the First International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, ESCAPE 2007, LNCS, vol. 4614, pp 1\u201311. Springer, Heidelberg (2007)","DOI":"10.1007\/978-3-540-74450-4_1"},{"issue":"3","key":"9644_CR5","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1287\/mnsc.3.3.279","volume":"3","author":"K Eisemann","year":"1957","unstructured":"Eisemann, K.: The trim problem. Manag. Sci. 3(3), 279\u2013284 (1957)","journal-title":"Manag. Sci."},{"issue":"34\u201336","key":"9644_CR6","doi-asserted-by":"crossref","first-page":"3073","DOI":"10.1016\/j.tcs.2010.04.037","volume":"411","author":"L Epstein","year":"2010","unstructured":"Epstein, L., Imreh, C., Levin, A.: Class constrained bin packing revisited. Theor. Comput. Sci. 411(34\u201336), 3073\u20133089 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9644_CR7","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W de la Vega","year":"1981","unstructured":"Fernandez, de la Vega, W., Lueker, G.S.: Bin packing can be solved within 1+\u03b5 in linear time. Combinatorica 1(4), 349\u2013355 (1981)","journal-title":"Combinatorica"},{"issue":"1","key":"9644_CR8","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1137\/0215016","volume":"15","author":"DK Friesen","year":"1986","unstructured":"Friesen, D.K., Langston, M.A.: Variable sized bin packing. SIAM J. Comput. 15(1), 222\u2013230 (1986)","journal-title":"SIAM J. Comput."},{"key":"9644_CR9","volume-title":"Computers and intractability. A guide to the theory of NP-completeness","author":"M Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman and Company, New York (1979)"},{"issue":"6","key":"9644_CR10","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1287\/opre.9.6.849","volume":"9","author":"P Gilmore","year":"1961","unstructured":"Gilmore, P., Gomory, R.: A linear programming approach to the cutting stock problem. Oper. Res. 9(6), 849\u2013859 (1961)","journal-title":"Oper. Res."},{"issue":"6","key":"9644_CR11","doi-asserted-by":"crossref","first-page":"863","DOI":"10.1287\/opre.11.6.863","volume":"11","author":"P Gilmore","year":"1963","unstructured":"Gilmore, P., Gomory, R.: A linear programming approach to the cutting stock problem\u2014Part II. Oper. Res. 11(6), 863\u2013888 (1963)","journal-title":"Oper. Res."},{"issue":"4","key":"9644_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-min resource sharing for structured concave optimization. SIAM J. Optim. 11(4), 1081\u20131091 (2001)","journal-title":"SIAM J. Optim."},{"key":"9644_CR13","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"OH Ibarra","year":"1975","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22, 463\u2013468 (1975)","journal-title":"J. ACM"},{"key":"9644_CR14","doi-asserted-by":"crossref","unstructured":"Jansen, K.: Approximation algorithms for min-max and max-min resource sharing problems, and applications. In: Bampis, E., Jansen, K., Kenyon, C. (eds.) Efficient approximation and online algorithms, LNCS, vol. 3484, pp 156\u2013202. Springer, Berlin (2006)","DOI":"10.1007\/11671541_6"},{"key":"9644_CR15","doi-asserted-by":"crossref","unstructured":"Jansen, K., Kraft, S.: An improved approximation scheme for variable-sized bin packing. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) Proceedings of the 37th international symposium on mathematical foundations of computer science, MFCS 2012, LNCS, vol. 7464, pp 529\u2013541. Springer, Heidelberg (2012)","DOI":"10.1007\/978-3-642-32589-2_47"},{"key":"9644_CR16","doi-asserted-by":"crossref","unstructured":"Jansen, K., Kraft, S.: An improved knapsack solver for column generation. In: Bulatov, A.A., Shur, A.M. (eds.) Proceedings of the 8th international computer science symposium in Russia, CSR 2013, LNCS, vol. 7913, pp 12\u201323. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-38536-0_2"},{"issue":"1\u20133","key":"9644_CR17","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1016\/S0304-3975(03)00363-3","volume":"306","author":"K Jansen","year":"2003","unstructured":"Jansen, K., Solis-Oba, R.: An asymptotic fully polynomial time approximation scheme for bin covering. Theor. Comput. Sci. 306(1\u20133), 543\u2013551 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9644_CR18","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1287\/mnsc.6.4.366","volume":"6","author":"LV Kantorovich","year":"1960","unstructured":"Kantorovich, L.V.: Mathematical methods of organizing and planning production. Manag. Sci. 6(4), 366\u2013422 (1960). Significantly enlarged and translated record of a report given in 1939","journal-title":"Manag. Sci."},{"key":"9644_CR19","first-page":"312","volume-title":"An efficient approximation scheme for the one-dimensional bin-packing problem. In: 23rd annual symposium on foundations of computer science (FOCS 1982)","author":"N Karmarkar","year":"1982","unstructured":"Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: 23rd annual symposium on foundations of computer science (FOCS 1982), pp 312\u2013320. IEEE Computer Society, Chicago (1982)"},{"key":"9644_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack Problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2004)"},{"issue":"4","key":"9644_CR21","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(4), 339\u2013356 (1979)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"9644_CR22","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/0377-2217(81)90175-2","volume":"8","author":"MJ Magazine","year":"1981","unstructured":"Magazine, M.J., Oguz, O.: A fully polynomial approximation algorithm for the 0-1 knapsack problem. Eur. J. Oper. Res. 8(3), 270\u2013273 (1981)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"9644_CR23","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1137\/0216012","volume":"16","author":"FD Murgolo","year":"1987","unstructured":"Murgolo, F.D.: An efficient approximation scheme for variable-sized bin packing. SIAM J. Comput. 16(1), 149\u2013161 (1987)","journal-title":"SIAM J. Comput."},{"key":"9644_CR24","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"SA Plotkin","year":"1995","unstructured":"Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9.: Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20, 257\u2013301 (1995)","journal-title":"Math. Oper. Res."},{"key":"9644_CR25","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1109\/FOCS.2013.11","volume-title":"Approximating bin packing within O(logOPT\u22c5 log logOPT) bins. In: 54th Annual IEEE symposium on foundations of computer science, FOCS 2013","author":"T Rothvo\u00df","year":"2013","unstructured":"Rothvo\u00df, T.: Approximating bin packing within O(logO P T\u22c5 log logO P T) bins. In: 54th Annual IEEE symposium on foundations of computer science, FOCS 2013, pp 20\u201329. IEEE Computer Society, Chicago (2013)"},{"issue":"1","key":"9644_CR26","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/s00224-007-9082-x","volume":"43","author":"H Shachnai","year":"2008","unstructured":"Shachnai, H., Tamir, T., Yehezkely, O.: Approximation schemes for packing with item fragmentation. Theory Comput. Syst. 43(1), 81\u201398 (2008)","journal-title":"Theory Comput. Syst."},{"key":"9644_CR27","doi-asserted-by":"crossref","unstructured":"Shachnai, H., Yehezkely, O.: Fast asymptotic FPTAS for packing fragmentable items with costs. In: Csuhaj-Varj\u00fa, E., \u00c9sik, Z. (eds.) Proceedings of the 16th international symposium on fundamentals of computation theory, FCT 2007, LNCS, vol. 4639, pp 482\u2013493. Springer, Heidelberg (2007)","DOI":"10.1007\/978-3-540-74240-1_42"},{"key":"9644_CR28","unstructured":"Shmonin, G.: Parameterised integer programming, integer cones, and related problems, Ph.D. thesis. Universit\u00e4t Paderborn (2007)"},{"key":"9644_CR29","doi-asserted-by":"crossref","unstructured":"Simchi-Levi, D.: New worst-case results for the bin-packing problem. Nav. Res. Logist. 41(4), 579\u2013585 (1994)","DOI":"10.1002\/1520-6750(199406)41:4<579::AID-NAV3220410409>3.0.CO;2-G"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9644-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-015-9644-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9644-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,29]],"date-time":"2019-08-29T21:44:47Z","timestamp":1567115087000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-015-9644-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,2]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,8]]}},"alternative-id":["9644"],"URL":"https:\/\/doi.org\/10.1007\/s00224-015-9644-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,2]]}}}