{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:33:05Z","timestamp":1725557585018},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540406716"},{"type":"electronic","value":"9783540451389"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45138-9_12","type":"book-chapter","created":{"date-parts":[[2010,6,22]],"date-time":"2010-06-22T22:41:48Z","timestamp":1277246508000},"page":"179-188","source":"Crossref","is-referenced-by-count":10,"title":["Completeness in Differential Approximation Classes"],"prefix":"10.1007","author":[{"given":"G.","family":"Ausiello","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C.","family":"Bazgan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Demange","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V. Th.","family":"Paschos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","unstructured":"Orponen, P., Mannila, H.: On approximation preserving reductions: complete problems and robust measures. Technical Report C-1987-28, Dept. of Computer Science, University of Helsinki, Finland (1987)"},{"key":"12_CR2","doi-asserted-by":"publisher","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. Inform. and Comput.\u00a093, 241\u2013262 (1991)","journal-title":"Inform. and Comput."},{"key":"12_CR3","doi-asserted-by":"publisher","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. System Sci.\u00a043, 425\u2013440 (1991)","journal-title":"J. Comput. System Sci."},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(94)00291-P","volume":"150","author":"G. Ausiello","year":"1995","unstructured":"Ausiello, G., Crescenzi, P., Protasi, M.: Approximate solutions of NP optimization problems. Theoret. Comput. Sci.\u00a0150, 1\u201355 (1995)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1007\/3-540-58715-2_135","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"P. Crescenzi","year":"1994","unstructured":"Crescenzi, P., Trevisan, L.: On approximation scheme preserving reducibility and its applications. In: Thiagarajan, P.S. (ed.) FSTTCS 1994. LNCS, vol.\u00a0880, pp. 330\u2013341. Springer, Heidelberg (1994)"},{"key":"12_CR6","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Languages and Programming","author":"G. Ausiello","year":"1977","unstructured":"Ausiello, G., D\u2019Atri, A., Protasi, M.: On the structure of combinatorial problems and structure preserving reductions. In: Salomaa, A., Steinby, M. (eds.) ICALP 1977. LNCS, vol.\u00a052. Springer, Heidelberg (1977)"},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0304-3975(95)00060-7","volume":"158","author":"M. Demange","year":"1996","unstructured":"Demange, M., Paschos, V.T.: On an approximation measure founded on the links between optimization and polynomial approximation theory. Theoret. Comput. Sci.\u00a0158, 117\u2013141 (1996)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR8","unstructured":"Ausiello, G., Protasi, M.: NP optimization problems and local optima graph theory. In: Alavi, Y., Schwenk, A. (eds.) Combinatorics and applications. Proc. 7th Quadriennal International Conference on the Theory and Applications of Graphs, vol.\u00a02, pp. 957\u2013975 (1995)"},{"key":"12_CR9","volume-title":"Complexity and approximation. Combinatorial optimization problems and their approximability properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and approximation. Combinatorial optimization problems and their approximability properties. Springer, Berlin (1999)"},{"key":"12_CR10","doi-asserted-by":"crossref","unstructured":"Ausiello, G., Bazgan, C., Demange, M., Paschos, V.T.: Completeness in differential approximation classes. Cahier du LAMSADE 204, LAMSADE, Universit\u00e9 Paris-Dauphine (2003), Available on http:\/\/www.lamsade.dauphine.fr\/cahiers.html","DOI":"10.1007\/978-3-540-45138-9_12"},{"key":"12_CR11","doi-asserted-by":"publisher","first-page":"1759","DOI":"10.1137\/S0097539796304220","volume":"28","author":"P. Crescenzi","year":"1999","unstructured":"Crescenzi, P., Kann, V., Silvestri, R., Trevisan, L.: Structure in approximation classes. SIAM J. Comput.\u00a028, 1759\u20131782 (1999)","journal-title":"SIAM J. Comput."},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/S0020-0190(01)00287-3","volume":"82","author":"J. Monnot","year":"2002","unstructured":"Monnot, J.: Differential approximation results for the traveling salesman and related problems. Inform. Process. Lett.\u00a082, 229\u2013235 (2002)","journal-title":"Inform. Process. Lett."},{"key":"12_CR13","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1006\/jagm.2001.1187","volume":"41","author":"R. Hassin","year":"2001","unstructured":"Hassin, R., Khuller, S.: z-approximations. J. Algorithms\u00a041, 429\u2013442 (2001)","journal-title":"J. Algorithms"},{"key":"12_CR14","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1016\/S0377-2217(02)00299-0","volume":"147","author":"C. Bazgan","year":"2003","unstructured":"Bazgan, C., Paschos, V.T.: Differential approximation for optimal satisfiability and related problems. European J. Oper. Res.\u00a0147, 397\u2013404 (2003)","journal-title":"European J. Oper. Res."},{"key":"12_CR15","unstructured":"Toulouse, S.: Approximation polynomiale: optima locaux et rapport diff\u00e9rentiel. PhD thesis, LAMSADE, Universit\u00e9 Paris-Dauphine (2001)"},{"key":"12_CR16","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0020-0190(95)00006-X","volume":"54","author":"G. Ausiello","year":"1995","unstructured":"Ausiello, G., Protasi, M.: Local search, reducibility and approximability of NPoptimization problems. Inform. Process. Lett.\u00a054, 73\u201379 (1995)","journal-title":"Inform. Process. Lett."},{"key":"12_CR17","unstructured":"Monnot, J., Paschos, V.T., Toulouse, S.: Optima locaux garantis pour l\u2019approximation differ\u00e9ntielle. Technical Report 203, LAMSADE, Universit\u00e9 Paris-Dauphine (2002), Available on http:\/\/www.lamsade.dauphine.fr\/cahdoc.html#cahiers"},{"key":"12_CR18","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/s001860200239","volume":"57","author":"J. Monnot","year":"2003","unstructured":"Monnot, J., Paschos, V.T., Toulouse, S.: Approximation algorithms for the traveling salesman problem. Mathematical Methods of Operations Research\u00a057, 387\u2013405 (2003)","journal-title":"Mathematical Methods of Operations Research"},{"key":"12_CR19","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1137\/S0097539795286612","volume":"28","author":"S. Khanna","year":"1998","unstructured":"Khanna, S., Motwani, R., Sudan, M., Vazirani, U.: On syntactic versus computational views of approximability. SIAM J. Comput.\u00a028, 164\u2013191 (1998)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45138-9_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T09:54:13Z","timestamp":1559210053000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45138-9_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540406716","9783540451389"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45138-9_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}