{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,14]],"date-time":"2024-12-14T05:09:13Z","timestamp":1734152953845,"version":"3.30.2"},"reference-count":45,"publisher":"EDP Sciences","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"published-print":{"date-parts":[[2002,10]]},"DOI":"10.1051\/ro:2003009","type":"journal-article","created":{"date-parts":[[2003,7,3]],"date-time":"2003-07-03T12:00:30Z","timestamp":1057233630000},"page":"311-350","source":"Crossref","is-referenced-by-count":0,"title":["Autour de nouvelles notions pour l'analyse des algorithmes d'approximation\u00a0: de la structure de NPO \u00e0 la structure des instances"],"prefix":"10.1051","volume":"36","author":[{"given":"Marc","family":"Demange","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vangelis","family":"Paschos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2003,7,15]]},"reference":[{"key":"R1","unstructured":"L. Alfandari,Approximation de probl\u00e8mes de couverture et de partitionnement de graphes, Ph.D. Thesis. LAMSADE, Universit\u00e9 Paris-Dauphine (1999)."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"N. Alon et N. Kahale, Approximating the independence numberviathe \u03b8-function.Math. Programming(1998).","DOI":"10.1007\/BF01581168"},{"key":"R3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0895480192240226","volume":"8","author":"Andre\u00e6","year":"1995","journal-title":"SIAM J. Discrete Math."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela et M. Protasi,Complexity and approximation. Combinatorial optimization problems and their approximability properties. Springer, Heidelberg (1999).","DOI":"10.1007\/978-3-642-58412-1"},{"key":"R5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(94)00291-P","volume":"150","author":"Ausiello","year":"1995","journal-title":"Theoret. Comput. Sci."},{"key":"R6","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/0022-0000(80)90046-X","volume":"21","author":"Ausiello","year":"1980","journal-title":"J. Comput. System Sci."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"M.A. Bender et C. Chekuri, Performance guarantees for the TSP with a parametrized triangle inequality, dansProc. WADS'99. Springer,Lecture Notes in Comput. Sci.1663(1999) 80-85.","DOI":"10.1007\/3-540-48447-7_10"},{"key":"R8","unstructured":"C. Berge,Graphs and hypergraphs.North Holland, Amsterdam (1973)."},{"key":"R9","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"Berman","year":"1977","journal-title":"SIAM J. Comput."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"H.-J. B\u00f6ckenhauer, J. Hromkovic, R. Klasing, S. Seibert et W. Unger,Towards the notion of stability of approximation algorithms and the traveling salesman problem, Report 31, Electr. Colloq. Computational Comp. (1999).","DOI":"10.1007\/3-540-46521-9_7"},{"key":"R11","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/S0020-0190(00)00089-2","volume":"75","author":"Approximation","year":"2000","journal-title":"Inform. Process. Lett."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"height 2pt depth -1.6pt width 23pt, An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle inequality, dansProc. STACS'00. Springer,Lecture Notes in Comput. Sci.(2000) 382-394.","DOI":"10.1007\/3-540-46541-3_32"},{"key":"R13","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1051\/ita:2000115","volume":"34","author":"B\u00f6ckenhauer","year":"2000","journal-title":"RAIRO: Theoret. Informatics Appl."},{"key":"R14","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/BF01994876","volume":"32","author":"Boppana","year":"1992","journal-title":"BIT"},{"key":"R15","unstructured":"N. Creignou,Temps lin\u00e9aire et probl\u00e8mes NP-complets, Ph.D. Thesis. Universit\u00e9 de Caen (1993)."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"P. Crescenzi, A short guide to approximation preserving reductions, dansProc. Conference on Computational Complexity(1997) 262-273.","DOI":"10.1109\/CCC.1997.612321"},{"key":"R17","unstructured":"P. Crescenzi, V. Kann, R. Silvestri et L. Trevisan,Structure in approximation classes, Technical Report TR96-066, Electronic Colloquium on Computational Complexity (1996). Available on www_address: http:\/\/www.eccc.uni-trier.de\/eccc\/"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"P. CRESCENZI ET A. PANCONESI, Completeness in approximation classes.SIAM J. Comput.(1991).","DOI":"10.1016\/0890-5401(91)90025-W"},{"key":"R19","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0304-3975(97)00099-6","volume":"209","author":"Demange","year":"1998","journal-title":"Theoret. Comput. Sci."},{"key":"R20","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/S0893-9659(99)00112-3","volume":"12","author":"Demange","year":"1999","journal-title":"Appl. Math. Lett."},{"key":"R21","first-page":"169","volume":"26","author":"Maximizing","year":"2001","journal-title":"Found. Comput. Decision Sci."},{"key":"R22","first-page":"51","volume":"135","author":"Demange","year":"1996","journal-title":"Math. Inf. Sci. Humaines"},{"key":"R23","unstructured":"height 2pt depth -1.6pt width 23pt,Towards a general formal framework for polynomial approximation.Cahier du LAMSADE177. LAMSADE, Universit\u00e9 Paris-Dauphine (2001)."},{"key":"R24","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1051\/ro:2003005","volume":"36","author":"Autour de","year":"2002","journal-title":"RAIRO: Oper. Res."},{"key":"R25","doi-asserted-by":"crossref","unstructured":"U. Feige et J. Kilian, Zero knowledge and the chromatic number, dansProc. Conference on Computational Complexity(1996) 278-287.","DOI":"10.1109\/CCC.1996.507690"},{"key":"R26","unstructured":"M.R. Garey et D.S. Johnson,Computers and intractability. A guide to the theory of NP-completeness. W. H. Freeman, San Francisco (1979)."},{"key":"R27","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0020-0190(93)90022-2","volume":"46","author":"Halld\u00f3rsson","year":"1993","journal-title":"Inform. Process. Lett."},{"key":"R28","unstructured":"height 2pt depth -1.6pt width 23pt,Approximations via partitioning, JAIST Research Report IS-RR-95-0003F. Japan Advanced Institute of Science and Technology, Japan (1995)."},{"key":"R29","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"H\u00e5stad","year":"1999","journal-title":"Acta Math."},{"key":"R30","doi-asserted-by":"crossref","unstructured":"D.S. Hochbaum,Approximation algorithms for NP-hard problems. PWS, Boston (1997).","DOI":"10.1145\/261342.571216"},{"key":"R31","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"Johnson","year":"1974","journal-title":"J. Comput. System Sci."},{"key":"R32","first-page":"317","volume":"1","author":"Kann","year":"1994","journal-title":"Nordic J. Comput."},{"key":"R33","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/274787.274791","volume":"45","author":"Karger","year":"1998","journal-title":"J. Assoc. Comput. Mach."},{"key":"R34","doi-asserted-by":"crossref","unstructured":"R.M. Karp, Reducibility among combinatorial problems, dansComplexity of computer computations, \u00e9dit\u00e9 par R.E. Miller et J.W. Thatcher, Plenum Press, New York (1972) 85-103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"R35","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1137\/S0097539795286612","volume":"28","author":"Khanna","year":"1998","journal-title":"SIAM J. Comput."},{"key":"R36","unstructured":"J. Lorenzo,Approximation des solutions et des valeurs des probl\u00e8mes NP-complets, Th\u00e8se de Doctorat. CERMSEM, Universit\u00e9 Paris I (en pr\u00e9paration)."},{"key":"R37","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1137\/0207010","volume":"7","author":"Lynch","year":"1978","journal-title":"SIAM J. Comput."},{"key":"R38","unstructured":"J. Monnot,Familles critiques d'instances et approximation polynomiale, Ph.D. Thesis. LAMSADE, Universit\u00e9 Paris-Dauphine (1998)."},{"key":"R39","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"Nemhauser","year":"1978","journal-title":"Math. Programming"},{"key":"R40","unstructured":"P. Orponen et H. Mannila,On approximation preserving reductions: Complete problems and robust measures, Tech. Rep. C-1987-28. Dept. of Computer Science, University of Helsinki, Finland (1987)."},{"key":"R41","unstructured":"C.H. Papadimitriou et K. Steiglitz,Combinatorial optimization: Algorithms and complexity. Prentice Hall, New Jersey (1981)."},{"key":"R42","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"Papadimitriou","year":"1991","journal-title":"J. Comput. System Sci."},{"key":"R43","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0304-3975(81)90081-5","volume":"15","author":"Paz","year":"1981","journal-title":"Theoret. Comput. Sci."},{"key":"R44","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1137\/0403025","volume":"3","author":"Simon","year":"1990","journal-title":"SIAM J. Discrete Math."},{"key":"R45","unstructured":"V. Vazirani,Approximation algorithms. Springer, Heidelberg (2001)."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ro.org\/10.1051\/ro:2003009\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,13]],"date-time":"2024-12-13T04:16:23Z","timestamp":1734063383000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ro.org\/10.1051\/ro:2003009"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,10]]},"references-count":45,"journal-issue":{"issue":"4"},"alternative-id":["ro2302"],"URL":"https:\/\/doi.org\/10.1051\/ro:2003009","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"1290-3868"}],"subject":[],"published":{"date-parts":[[2002,10]]}}}