{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,17]],"date-time":"2026-04-17T17:00:30Z","timestamp":1776445230060,"version":"3.51.2"},"reference-count":26,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2018,2,1]],"date-time":"2018-02-01T00:00:00Z","timestamp":1517443200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2022,2,1]],"date-time":"2022-02-01T00:00:00Z","timestamp":1643673600000},"content-version":"vor","delay-in-days":1461,"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["JA612\/14-2"],"award-info":[{"award-number":["JA612\/14-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["European Journal of Combinatorics"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1016\/j.ejc.2017.07.016","type":"journal-article","created":{"date-parts":[[2017,9,1]],"date-time":"2017-09-01T12:00:18Z","timestamp":1504267218000},"page":"148-174","update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":12,"special_numbering":"C","title":["A faster FPTAS for the Unbounded Knapsack Problem"],"prefix":"10.1016","volume":"68","author":[{"given":"Klaus","family":"Jansen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan E.J.","family":"Kraft","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/j.ejc.2017.07.016_b1","series-title":"Dynamic Programming","author":"Bellman","year":"1957"},{"issue":"4","key":"10.1016\/j.ejc.2017.07.016_b2","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1142\/S1793830911001413","article-title":"Approximation algorithms for multiple strip packing and scheduling parallel jobs in platforms","volume":"3","author":"Bougeret","year":"2011","journal-title":"Discrete Math. Algorithms Appl."},{"key":"10.1016\/j.ejc.2017.07.016_b3","series-title":"Logspace Versions of the Theorems of Bodlaender and Courcelle, Tech. Rep. 62, Electronic Colloquium on Computational Complexity (ECCC)","author":"Elberfeld","year":"2010"},{"key":"10.1016\/j.ejc.2017.07.016_b4","series-title":"Space-Efficient Approximations for Subset Sum, Tech. Rep. 180, Electronic Colloquium on Computational Complexity (ECCC)","author":"G\u00e1l","year":"2014"},{"key":"10.1016\/j.ejc.2017.07.016_b5","series-title":"Computers and Intractability. A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"issue":"6","key":"10.1016\/j.ejc.2017.07.016_b6","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1287\/opre.9.6.849","article-title":"A linear programming approach to the cutting-stock problem","volume":"9","author":"Gilmore","year":"1961","journal-title":"Oper. Res."},{"issue":"4","key":"10.1016\/j.ejc.2017.07.016_b7","doi-asserted-by":"crossref","first-page":"1081","DOI":"10.1137\/S1052623499358689","article-title":"Approximate max-min resource sharing for structured concave optimization","volume":"11","author":"Grigoriadis","year":"2001","journal-title":"SIAM J. Optim."},{"issue":"4","key":"10.1016\/j.ejc.2017.07.016_b8","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/321906.321909","article-title":"Fast approximation algorithms for the Knapsack and sum of subset problems","volume":"22","author":"Ibarra","year":"1975","journal-title":"J. ACM"},{"key":"10.1016\/j.ejc.2017.07.016_b9","series-title":"Efficient Approximation and Online Algorithms","first-page":"156","article-title":"Approximation algorithms for min-max and max-min resource sharing problems, and applications","volume":"vol. 3484","author":"Jansen","year":"2006"},{"key":"10.1016\/j.ejc.2017.07.016_b10","series-title":"Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science, MFCS 2012","first-page":"529","article-title":"An improved approximation scheme for variable-sized bin packing","volume":"vol. 7464","author":"Jansen","year":"2012"},{"key":"10.1016\/j.ejc.2017.07.016_b11","series-title":"Proceedings of the 8th International Computer Science Symposium in Russia, CSR 2013","first-page":"12","article-title":"An improved Knapsack solver for column generation","volume":"vol. 7913","author":"Jansen","year":"2013"},{"key":"10.1016\/j.ejc.2017.07.016_b12","series-title":"Proceedings of the 26th International Workshop on Combinatorial Algorithms, IWOCA 2015","first-page":"274","article-title":"A faster FPTAS for the unbounded Knapsack problem","volume":"vol. 9538","author":"Jansen","year":"2016"},{"key":"10.1016\/j.ejc.2017.07.016_b13","unstructured":"D.M. Kane, (2010) Unary subset-sum is in logspace, CoRR, https:\/\/2.zoppoz.workers.dev:443\/https\/arxiv.org\/abs\/1012.1336."},{"key":"10.1016\/j.ejc.2017.07.016_b14","series-title":"Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, FOCS 1982","first-page":"312","article-title":"An efficient approximation scheme for the one-dimensional bin-packing problem","author":"Karmarkar","year":"1982"},{"issue":"2","key":"10.1016\/j.ejc.2017.07.016_b15","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/S0022-0000(03)00006-0","article-title":"An efficient fully polynomial approximation scheme for the subset-sum problem","volume":"66","author":"Kellerer","year":"2003","journal-title":"J. Comput. System Sci."},{"issue":"1","key":"10.1016\/j.ejc.2017.07.016_b16","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1023\/A:1009813105532","article-title":"A new fully polynomial time approximation scheme for the Knapsack problem","volume":"3","author":"Kellerer","year":"1999","journal-title":"J. Comb. Optim."},{"issue":"1","key":"10.1016\/j.ejc.2017.07.016_b17","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1023\/B:JOCO.0000021934.29833.6b","article-title":"Improved dynamic programming in connection with an FTPAS for the Knapsack problem","volume":"8","author":"Kellerer","year":"2004","journal-title":"J. Comb. Optim."},{"key":"10.1016\/j.ejc.2017.07.016_b18","series-title":"Knapsack Problems","author":"Kellerer","year":"2004"},{"issue":"4","key":"10.1016\/j.ejc.2017.07.016_b19","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1287\/moor.25.4.645.12118","article-title":"A near-optimal solution to a two-dimensional cutting stock problem","volume":"25","author":"Kenyon","year":"2000","journal-title":"Math. Oper. Res."},{"key":"10.1016\/j.ejc.2017.07.016_b20","series-title":"Improved Approximation Algorithms for Packing and Scheduling Problems (Ph.D. thesis)","author":"Kraft","year":"2016"},{"issue":"4","key":"10.1016\/j.ejc.2017.07.016_b21","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1287\/moor.4.4.339","article-title":"Fast approximation algorithms for Knapsack problems","volume":"4","author":"Lawler","year":"1979","journal-title":"Math. Oper. Res."},{"key":"10.1016\/j.ejc.2017.07.016_b22","series-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010","first-page":"321","article-title":"Saving space by algebraization","author":"Lokshtanov","year":"2010"},{"issue":"3","key":"10.1016\/j.ejc.2017.07.016_b23","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/0377-2217(81)90175-2","article-title":"A fully polynomial approximation algorithm for the 0-1 knapsack problem","volume":"8","author":"Magazine","year":"1981","journal-title":"European J. Oper. Res."},{"issue":"2","key":"10.1016\/j.ejc.2017.07.016_b24","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1287\/moor.20.2.257","article-title":"Fast approximation algorithms for fractional packing and covering problems","volume":"20","author":"Plotkin","year":"1995","journal-title":"Math. Oper. Res."},{"key":"10.1016\/j.ejc.2017.07.016_b25","series-title":"Proceedings of the 16th International Symposium on Fundamentals of Computation Theory, FCT 2007","first-page":"482","article-title":"Fast asymptotic FPTAS for packing fragmentable items with costs","volume":"vol. 4639","author":"Shachnai","year":"2007"},{"issue":"1\u20132","key":"10.1016\/j.ejc.2017.07.016_b26","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1016\/j.ipl.2011.10.003","article-title":"A note on the Kenyon-Remila strip-packing algorithm","volume":"112","author":"Sviridenko","year":"2012","journal-title":"Inform. Process. Lett."}],"container-title":["European Journal of Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/api.elsevier.com\/content\/article\/PII:S0195669817301245?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/api.elsevier.com\/content\/article\/PII:S0195669817301245?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,6,7]],"date-time":"2022-06-07T15:34:31Z","timestamp":1654616071000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/linkinghub.elsevier.com\/retrieve\/pii\/S0195669817301245"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2]]},"references-count":26,"alternative-id":["S0195669817301245"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1016\/j.ejc.2017.07.016","relation":{},"ISSN":["0195-6698"],"issn-type":[{"value":"0195-6698","type":"print"}],"subject":[],"published":{"date-parts":[[2018,2]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"A faster FPTAS for the Unbounded Knapsack Problem","name":"articletitle","label":"Article Title"},{"value":"European Journal of Combinatorics","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1016\/j.ejc.2017.07.016","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2017 Elsevier Ltd.","name":"copyright","label":"Copyright"}]}}