{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T02:51:34Z","timestamp":1778295094978,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540587156","type":"print"},{"value":"9783540490548","type":"electronic"}],"license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"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":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58715-2_135","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:42:18Z","timestamp":1330274538000},"page":"330-341","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["On approximation scheme preserving reductibility and its applications"],"prefix":"10.1007","author":[{"given":"Pierluigi","family":"Crescenzi","sequence":"first","affiliation":[]},{"given":"Luca","family":"Trevisan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"27_CR1","unstructured":"Arora S., Lund C., Motwani R., Sudan M., Szegedy M.: Proof verification and hardness of approximation problems. Proc. 33-rd Ann. IEEE Symp. on Foundations of Computer Science (1992) 14\u201323"},{"key":"27_CR2","unstructured":"Ausiello G., Crescenzi P., Protasi M.: Approximate Solution of NP Optimization Problems Technical Report SI\/RR-94\/03, Universita di Roma \u201cLa Sapienza\u201d (1994)"},{"key":"27_CR3","unstructured":"Crescenzi P., Kann V., Trevisan L.; On the structure of the classes NPO and APX. Manuscript in preparation (1994)"},{"key":"27_CR4","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0890-5401(91)90025-W","volume":"93","author":"P. Crescenzi","year":"1991","unstructured":"Crescenzi P., Panconesi A.: Completeness in approximation classes. Information and Computation 93 (1991) 241\u2013262","journal-title":"Information and Computation"},{"key":"27_CR5","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0020-0190(90)90188-4","volume":"33","author":"P. Crescenzi","year":"1990","unstructured":"Crescenzi P., Silvestri R.: Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems. Information Processing Letters 33 (1990) 221\u2013226","journal-title":"Information Processing Letters"},{"key":"27_CR6","unstructured":"Downey R.G., Fellows M.R.: Fixed parameter intractability. Proc. 7-th Structure in Complexity Theory (1992) 36\u201349"},{"key":"27_CR7","doi-asserted-by":"crossref","unstructured":"Hemaspaandra, L.A.: Complexity theory column 5: the not-ready-for-prime-time conjectures. SIGACT News (1994)","DOI":"10.1145\/181462.181463"},{"key":"27_CR8","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson D.S.: Approximation algorithms for combinatorial problems. J. Comput. and Syst. Sci. 9 (1974) 256\u2013278","journal-title":"J. Comput. and Syst. Sci."},{"key":"27_CR9","volume-title":"PhD thesis","author":"V. Kann","year":"1992","unstructured":"Kann V.: On the approximability of NP-complete optimization problems. PhD thesis, Department of Numerical Analysis and Computing Science, Royal Institute of technology, Stockholm (1992)"},{"key":"27_CR10","unstructured":"Khanna S., Motwani R., Sudan M., Vazirani U.: On syntactic versus computational views of approximability. Proc. 35-th Ann. IEEE Symp. on Foundations of Computer Science (1994) to appear"},{"key":"27_CR11","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M.W. Krentel","year":"1988","unstructured":"Krentel M.W.: The complexity of optimization problems. J. Comput. and Syst. Sci. 36 (1988) 490\u2013509","journal-title":"J. Comput. and Syst. Sci."},{"key":"27_CR12","unstructured":"Orponen P., Mannila H.: On approximation preserving reductions: complete problems and robust measures. Technical Report C-1987-28, Department of Computer Science, University of Helsinki (1987)"},{"key":"27_CR13","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou C.H., Yannakakis M.: Optimization, approximation, and complexity classes. J. Comput. and Syst. Sci. 43 (1991), 425\u2013440","journal-title":"J. Comput. and Syst. Sci."},{"key":"27_CR14","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0304-3975(81)90081-5","volume":"15","author":"A. Paz","year":"1981","unstructured":"Paz A., Moran S.: Non deterministic polynomial optimization problems and their approximations. Theoret. Comput. Sci. 15 (1981) 251\u2013277","journal-title":"Theoret. Comput. Sci."},{"key":"27_CR15","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L. Valiant","year":"1976","unstructured":"Valiant L.: Relative complexity of checking and evaluating. Information Processing Letters 5 (1976) 20\u201323","journal-title":"Information Processing Letters"},{"key":"27_CR16","unstructured":"Yannakakis M.: On the approximation of maximum satisfiability. Proc. 3-rd ACM-SIAM Symp. on Discrete Algorithms (1992) 1\u20139"}],"container-title":["Lecture Notes in Computer Science","Foundation of Software Technology and Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58715-2_135","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T23:16:50Z","timestamp":1578525410000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58715-2_135"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540587156","9783540490548"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-58715-2_135","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}