{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:44:19Z","timestamp":1749825859962},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642299513"},{"type":"electronic","value":"9783642299520"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29952-0_17","type":"book-chapter","created":{"date-parts":[[2012,5,3]],"date-time":"2012-05-03T06:14:09Z","timestamp":1336025649000},"page":"131-142","source":"Crossref","is-referenced-by-count":7,"title":["Constant-Time Approximation Algorithms for the Knapsack Problem"],"prefix":"10.1007","author":[{"given":"Hiro","family":"Ito","sequence":"first","affiliation":[]},{"given":"Susumu","family":"Kiyoshima","sequence":"additional","affiliation":[]},{"given":"Yuichi","family":"Yoshida","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"17_CR1","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1016\/S0022-0000(03)00008-4","volume":"67","author":"N. Alon","year":"2003","unstructured":"Alon, N., de la Vega, W., Kannan, R., Karpinski, M.: Random sampling and approximation of MAX-CSPs. Journal of Computer and System Sciences\u00a067(2), 212\u2013243 (2003)","journal-title":"Journal of Computer and System Sciences"},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Karger, D., Karpinski, M.: Polynomial time approximation schemes for dense instances of np-hard problems. In: Proc. 27th Annual ACM Symposium on Theory of Computing (STOC), pp. 284\u2013293. ACM (1995)","DOI":"10.1145\/225058.225140"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z., Kumar, R., Sivakumar, D.: Sampling algorithms: lower bounds and applications. In: Proc. 33rd Annual ACM Symposium on Theory of Computing, pp. 266\u2013275 (2001)","DOI":"10.1145\/380752.380810"},{"issue":"47-49","key":"17_CR4","doi-asserted-by":"publisher","first-page":"5082","DOI":"10.1016\/j.tcs.2009.08.006","volume":"410","author":"T. Batu","year":"2009","unstructured":"Batu, T., Berenbrink, P., Sohler, C.: A sublinear-time approximation scheme for bin packing. Theoretical Computer Science\u00a0410(47-49), 5082\u20135092 (2009)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"17_CR5","doi-asserted-by":"publisher","first-page":"1370","DOI":"10.1137\/S0097539702403244","volume":"34","author":"B. Chazelle","year":"2005","unstructured":"Chazelle, B., Rubinfeld, R., Trevisan, L.: Approximating the minimum spanning tree weight in sublinear time. SIAM Journal on Computing\u00a034(6), 1370\u20131379 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"17_CR6","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. (1979)"},{"key":"17_CR7","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 sum of subset problems. Journal of the ACM\u00a022, 463\u2013468 (1975)","journal-title":"Journal of the ACM"},{"issue":"2","key":"17_CR8","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1016\/S0022-0000(03)00006-0","volume":"66","author":"H. Kellerer","year":"2003","unstructured":"Kellerer, H., Mansini, R., Pferschy, U., Speranza, M.G.: An efficient fully polynomial approximation scheme for the subset-sum problem. Journal of Computer and System Sciences\u00a066(2), 349\u2013370 (2003)","journal-title":"Journal of Computer and System Sciences"},{"key":"17_CR9","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1023\/A:1009813105532","volume":"3","author":"H. Kellerer","year":"1999","unstructured":"Kellerer, H., Pferschy, U.: A new fully polynomial time approximation scheme for the knapsack problem. Journal of Combinatorial Optimization\u00a03, 59\u201371 (1999)","journal-title":"Journal of Combinatorial Optimization"},{"key":"17_CR10","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1023\/B:JOCO.0000021934.29833.6b","volume":"8","author":"H. Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U.: Improved dynamic programming in connection with an FPTAS for the knapsack problem. Journal of Combinatorial Optimization\u00a08, 5\u201311 (2004)","journal-title":"Journal of Combinatorial Optimization"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer (2004)","DOI":"10.1007\/978-3-540-24777-7"},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"Lawler, E.L.: Fast approximation algorithms for knapsack problems. In: Proc. 18th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 206\u2013213 (1977)","DOI":"10.1109\/SFCS.1977.11"},{"issue":"3","key":"17_CR13","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0377-2217(81)90175-2","volume":"8","author":"M. Magazine","year":"1981","unstructured":"Magazine, M., Oguz, O.: A fully polynomial approximation algorithm for the 0-1 knapsack problem. European Journal of Operational Research\u00a08(3), 270\u2013273 (1981)","journal-title":"European Journal of Operational Research"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"Nguyen, H.N., Onak, K.: Constant-time approximation algorithms via local improvements. In: Proc. 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 327\u2013336 (2008)","DOI":"10.1109\/FOCS.2008.81"},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"Yoshida, Y.: Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP. In: Proc. 43rd Annual ACM Symposium on Theory of Computing (STOC), pp. 665\u2013674 (2011)","DOI":"10.1145\/1993636.1993725"},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"Yoshida, Y., Yamamoto, M., Ito, H.: An improved constant-time approximation algorithm for maximum matchings. In: Proc. 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 225\u2013234 (2009)","DOI":"10.1145\/1536414.1536447"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29952-0_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:22:44Z","timestamp":1620127364000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-29952-0_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642299513","9783642299520"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29952-0_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}