{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T04:04:06Z","timestamp":1746331446292,"version":"3.40.4"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,6,15]],"date-time":"2014-06-15T00:00:00Z","timestamp":1402790400000},"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":[[2015,2]]},"DOI":"10.1007\/s00224-014-9550-z","type":"journal-article","created":{"date-parts":[[2014,6,19]],"date-time":"2014-06-19T09:26:58Z","timestamp":1403170018000},"page":"372-393","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Hardness of Approximation for Knapsack Problems"],"prefix":"10.1007","volume":"56","author":[{"given":"Harry","family":"Buhrman","sequence":"first","affiliation":[]},{"given":"Bruno","family":"Loff","sequence":"additional","affiliation":[]},{"given":"Leen","family":"Torenvliet","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,6,15]]},"reference":[{"key":"9550_CR1","unstructured":"Bach, E., Shallit, J.: Algorithmic Number Theory I: Efficient Algorithms. Cambridge University Press (1996)"},{"issue":"1","key":"9550_CR2","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"DA Barrington","year":"1989","unstructured":"Barrington, D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC 1. J. Comput. Syst. Sci. 38(1), 150\u2013164 (1989)","journal-title":"J. Comput. Syst. Sci."},{"issue":"9","key":"9550_CR3","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1073\/pnas.39.9.947","volume":"39","author":"R Bellman","year":"1953","unstructured":"Bellman, R.: Bottleneck problems and dynamic programming. Proc. Natl. Acad. Sci. USA 39(9), 947\u2013951 (1953)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"9550_CR4","doi-asserted-by":"crossref","unstructured":"Buss, S. R.: The boolean formula value problem is in ALOGTIME. In: Proceedings of the 19th STOC, pp. 123\u2013131 (1987)","DOI":"10.1145\/28395.28409"},{"key":"9550_CR5","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1137\/0221046","volume":"21","author":"SR Buss","year":"1992","unstructured":"Buss, S.R., Cook, S.A., Gupta, A., Ramachandran, V.: An optimal parallel algorithm for formula evaluation. SIAM J. Comput. 21, 755\u2013780 (1992)","journal-title":"SIAM J. Comput."},{"key":"9550_CR6","unstructured":"Crescenzi, P., Kann, V.: A compendium of NP optimization problems. http:\/\/www.nada.kth.se\/viggo\/problemlist\/compendium.html (2005)"},{"key":"9550_CR7","doi-asserted-by":"crossref","unstructured":"Cygan, M., Dell, H., Lokshtanov, D., Marx, D, Nederlof, J, Okamoto, Y, Paturi, R, Saurabh, S, Wahlstr\u00f6m, M: On problems as hard as CNF-SAT. In: Proceedings of the 27th CCC, pp. 74\u201384 (2012)","DOI":"10.1109\/CCC.2012.36"},{"issue":"4","key":"9550_CR8","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J: Some optimal inapproximability results. J. ACM 48(4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"key":"9550_CR9","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1137\/0217033","volume":"17","author":"SS Hochbaum","year":"1988","unstructured":"Hochbaum, S.S., Shmoys, D.B.: A polynomial approximation scheme for machine scheduling on uniform processors: Using the dual approach. SIAM J. Comput. 17, 539\u2013551 (1988)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9550_CR10","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1145\/321812.321823","volume":"20","author":"E Horowitz","year":"1974","unstructured":"Horowitz, E., Sahni, S.: Computing partitions with an application to the subset-sum problem. J. ACM 20(2), 277\u2013292 (1974)","journal-title":"J. ACM"},{"key":"9550_CR11","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Paturi, R.: The complexity of k-SAT. In: Proceedings of the 14th CCC, pp. 237\u2013240 (1999)","DOI":"10.1109\/CCC.1999.766282"},{"issue":"4","key":"9550_CR12","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"9550_CR13","doi-asserted-by":"crossref","unstructured":"Lewin, M., Livnar, D, Zwick, U: Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems. In: Proceedings of the 9th ICPO, pp. 67\u201382 (2002)","DOI":"10.1007\/3-540-47867-1_6"},{"key":"9550_CR14","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Nederlof, J.: Saving space by algebraization. In: Proceedings of the 42nd STOC, pp. 321\u2013330 (2010)","DOI":"10.1145\/1806689.1806735"},{"issue":"4","key":"9550_CR15","doi-asserted-by":"crossref","first-page":"1460","DOI":"10.1137\/S0097539794282930","volume":"28","author":"K Mulmuley","year":"1999","unstructured":"Mulmuley, K.: Lower bounds in a parallel model without bit operations. SIAM J. Comput. 28(4), 1460\u20131509 (1999)","journal-title":"SIAM J. Comput."},{"key":"9550_CR16","unstructured":"Myasnikov, A., Nikolaev, A., Ushakov, A.: Knapsack problems in groups. ArXiv: 1302.5671 (2013)"},{"key":"9550_CR17","doi-asserted-by":"crossref","unstructured":"Nederlof, J, Leeuwen, E.J.v., Zwaan, R.v.d.: Reducing a target interval to a few exact queries. In: Proceedings of the 37th MFCS, pp. 718\u2013727 (2012)","DOI":"10.1007\/978-3-642-32589-2_62"},{"key":"9550_CR18","doi-asserted-by":"crossref","unstructured":"Raz, R, Safra, S: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th STOC, pp. 475\u2013484 (1997)","DOI":"10.1145\/258533.258641"},{"key":"9550_CR19","doi-asserted-by":"crossref","unstructured":"Sen, S: The hardness of speeding-up knapsack. Technical report, BRICS (1998)","DOI":"10.7146\/brics.v5i14.19286"},{"key":"9550_CR20","doi-asserted-by":"crossref","unstructured":"Stockmeyer, LJ., Meyer, AR.: Word problems requiring exponential time. In: Proceedings of the 5th STOC, pp. 1\u20139 (1973)","DOI":"10.1145\/800125.804029"},{"key":"9550_CR21","doi-asserted-by":"crossref","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer (2004)","DOI":"10.1007\/978-3-662-04565-7"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9550-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9550-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9550-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T11:36:39Z","timestamp":1746272199000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9550-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,15]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,2]]}},"alternative-id":["9550"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9550-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2014,6,15]]}}}