{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,14]],"date-time":"2025-07-14T02:35:56Z","timestamp":1752460556676},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540514985"},{"type":"electronic","value":"9783540481805"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51498-8_11","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:00:03Z","timestamp":1330203603000},"page":"116-126","source":"Crossref","is-referenced-by-count":6,"title":["Completeness in approximation classes"],"prefix":"10.1007","author":[{"given":"Pierluigi","family":"Crescenzi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alessandro","family":"Panconesi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"G.Ausiello \u2014 A. Marchetti Spaccamela \u2014 M. Protasi \u201cToward a unified approach for the classification of NP-complete problems\u201d TCS 12 1980","DOI":"10.1016\/0304-3975(80)90006-7"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"S.A. Cook \u201cThe complexity of theorem-proving procedures\u201d Proc. 3rd ACM STOC 1971","DOI":"10.1145\/800157.805047"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"W.Fernandez De La Vega \u2014 G.S. Lueker \u201cBin Packing can be solved within 1 + \u03b5 in linear time\u201d Combinatorica 1 1981","DOI":"10.1007\/BF02579456"},{"key":"11_CR4","volume-title":"Computers and Intractability: a guide to the theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"M.R. Garey \u2014 D. Johnson \u201cComputers and Intractability: a guide to the theory of NP-completeness\u201d Freeman, San Francisco 1979"},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"S.Homer \u201cOn Simple And Creative Sets in NP\u201d TCS 47 1986","DOI":"10.1016\/0304-3975(86)90144-1"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"D.Hochbaum \u2014 D.Shmoys \u201cUsing Dual Approximation Algorithms for Scheduling problems: theoretical and practical results\u201d JACM 34 1987","DOI":"10.1145\/7531.7535"},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"O.H. Ibarra \u2014 C.E. Kim \u201cFast approximation for the Knapsack and Sum of Subset problems\u201d JACM 22 1975","DOI":"10.1145\/321906.321909"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"D.Johnson \u201cApproximation algorithms for combinatorial problems\u201d Proc. 5th ACM STOC 1973","DOI":"10.1145\/800125.804034"},{"key":"11_CR9","unstructured":"M.W. Krentel \u201cThe Complexity of Optimization Problems\u201d PhD Thesis, Cornell University May 87"},{"key":"11_CR10","unstructured":"B.Korte \u2014 R.Schrader \u201cOn the existence of fast approximation schemes\u201d NON LINEAR PROGRAMMING 4 1981"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"R. Ladner \u201cOn The Structure Of Polynomial Time Reducibility\u201d JACM 22 1975","DOI":"10.1145\/321864.321877"},{"key":"11_CR12","unstructured":"P.Orponen \u2014 H.Mannila \u201cOn approximation preserving reductions: complete problems and robust measures\u201d Technical Report, University of Helsinki 1987"},{"key":"11_CR13","unstructured":"A.Paz and S.Moran \u201cNP-optimization problems and their approximation\u201d Proc. 4th ICALP 1977"},{"key":"11_CR14","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"C. Papadimitriou","year":"1982","unstructured":"C. Papadimitriou \u2014 K. Steiglitz \u201cCombinatorial Optimization: Algorithms and Complexity\u201d Prentice-Hall, Englewood Cliffs, New Jersey 1982"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"S.K. Sahni \u201cAlgorithms for scheduling indepent tasks\u201d JACM 23 1976","DOI":"10.1145\/321921.321934"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51498-8_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:21:32Z","timestamp":1605648092000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51498-8_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540514985","9783540481805"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-51498-8_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}