{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,15]],"date-time":"2024-12-15T05:10:04Z","timestamp":1734239404497,"version":"3.30.2"},"reference-count":41,"publisher":"EDP Sciences","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"published-print":{"date-parts":[[2002,7]]},"DOI":"10.1051\/ro:2003005","type":"journal-article","created":{"date-parts":[[2003,11,19]],"date-time":"2003-11-19T08:45:45Z","timestamp":1069231545000},"page":"237-277","source":"Crossref","is-referenced-by-count":2,"title":["Autour de nouvelles notions pour l'analyse des algorithmes d'approximation\u00a0: formalisme unifi\u00e9 et classes d'approximation"],"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,4,15]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan et M. Szegedy, Proof verification and intractability of approximation problems, inProc. FOCS'92(1992) 14-23.","key":"R1","DOI":"10.1109\/SFCS.1992.267823"},{"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, Heildelberg (1999).","key":"R2","DOI":"10.1007\/978-3-642-58412-1_1"},{"unstructured":"C. Berge,Graphs and hypergraphs. North Holland, Amsterdam (1973).","key":"R3"},{"unstructured":"P. Berman et M. F\u00fcrer, Approximating maximum independent set in bounded degree graphs, inProc. Symposium on Discrete Algorithms(1994) 365-371.","key":"R4"},{"key":"R5","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/BF01994876","volume":"32","author":"Boppana","year":"1992","journal-title":"BIT"},{"key":"R6","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"Chv\u00e1tal","year":"1979","journal-title":"Math. Oper. Res."},{"doi-asserted-by":"crossref","unstructured":"S.A. Cook, The complexity of theorem-proving procedures, inProc. STOC'71(1971) 151-158.","key":"R7","DOI":"10.1145\/800157.805047"},{"key":"R8","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":"R9","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":"R10","first-page":"169","volume":"26","author":"Maximizing","year":"2001","journal-title":"Found. Comput. Decision Sci."},{"key":"R11","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0304-3975(95)00060-7","volume":"158","author":"Demange","year":"1996","journal-title":"Theoret. Comput. Sci."},{"key":"R12","first-page":"51","volume":"135","author":"Valeurs","year":"1996","journal-title":"Math. Inf. Sci. Humaines"},{"unstructured":"height 2pt depth -1.6pt width 23pt, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO \u00e0 la structure des instances.RAIRO: Oper. Res.(\u00e0 para\u00eetre).","key":"R13"},{"key":"R14","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/S0893-9659(97)00044-X","volume":"10","author":"Improved","year":"1997","journal-title":"Appl. Math. Lett."},{"unstructured":"height 2pt depth -1.6pt width 23pt,Towards a general formal framework for polynomial approximation. LAMSADE, Universit\u00e9 Paris-Dauphine,Cahier du LAMSADE177(2001).","key":"R15"},{"doi-asserted-by":"crossref","unstructured":"R. Duh et M. F\u00fcrer, Approximation ofk-set cover by semi-local optimization, inProc. STOC'97(1997) 256-265.","key":"R16","DOI":"10.1145\/258533.258599"},{"doi-asserted-by":"crossref","unstructured":"U. Feige et J. Kilian, Zero knowledge and the chromatic number, inProc. Conference on Computational Complexity(1996) 278-287.","key":"R17","DOI":"10.1109\/CCC.1996.507690"},{"key":"R18","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0012-365X(82)90130-3","volume":"40","author":"Fernandez de","year":"1982","journal-title":"Discrete Math."},{"unstructured":"M.R. Garey et D.S. Johnson,Computers and intractability. A guide sto the theory of NP-completeness. W.H. Freeman, San Francisco (1979).","key":"R19"},{"key":"R20","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0020-0190(93)90246-6","volume":"45","author":"Halld\u00f3rsson","year":"1993","journal-title":"Inform. Process. Lett."},{"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":"R21"},{"unstructured":"height 2pt depth -1.6pt width 23pt, Approximatingk-set cover and complementary graph coloring, inProc. International Integer Programming and Combinatorial Optimization Conference. Springer Verlag,Lecture Notes in Comput. Sci.1084(1996) 118-131.","key":"R22"},{"doi-asserted-by":"crossref","unstructured":"M.M. Halld\u00f3rsson et J. Radhakrishnan, Greed is good: Approximating independent sets in sparse and bounded-degree graphs, inProc. STOC'94(1994) 439-448.","key":"R23","DOI":"10.1145\/195058.195221"},{"key":"R24","first-page":"475","volume":"1","author":"Improved","year":"1994","journal-title":"Nordic J. Comput."},{"key":"R25","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0020-0190(94)00113-8","volume":"52","author":"Hassin","year":"1994","journal-title":"Inform. Process. Lett."},{"key":"R26","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"H\u00e5stad","year":"1999","journal-title":"Acta Math."},{"key":"R27","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"Hochbaum","year":"1983","journal-title":"Discrete Appl. Math."},{"unstructured":"height 2pt depth -1.6pt width 23pt,Approximation algorithms for NP-hard problems. PWS, Boston (1997).","key":"R28"},{"key":"R29","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"Ibarra","year":"1975","journal-title":"J. Assoc. Comput. Mach."},{"key":"R30","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."},{"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.","key":"R31","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"R32","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1137\/S0097539795286612","volume":"28","author":"Khanna","year":"1998","journal-title":"SIAM J. Comput."},{"unstructured":"H.R. Lewis et C.H. Papadimitriou,Elements of the theory of computation. Prentice-Hall (1981).","key":"R33"},{"key":"R34","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"Lund","year":"1994","journal-title":"J. Assoc. Comput. Mach."},{"unstructured":"R. Motwani,Lecture notes on approximation algorithms, Vol. I. Stanford University (1993).","key":"R35"},{"key":"R36","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"Nemhauser","year":"1978","journal-title":"Math. Programming"},{"unstructured":"C.H. Papadimitriou et K. Steiglitz,Combinatorial optimization: Algorithms and complexity. Prentice Hall, New Jersey (1981).","key":"R37"},{"doi-asserted-by":"crossref","unstructured":"R. Raz et S. Safra, A sub-constant error probability low-degree test and a sub-constant error probability PCP characterization of NP, inProc. STOC'97(1997) 475-484.","key":"R38","DOI":"10.1145\/258533.258641"},{"key":"R39","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1002\/1520-6750(199406)41:4<579::AID-NAV3220410409>3.0.CO;2-G","volume":"41","author":"Simchi-Levi","year":"1994","journal-title":"Naval Res. Logistics"},{"key":"R40","first-page":"436","volume":"48","author":"Tur\u00e1n","year":"1941","journal-title":"Mat. Fiz. Lapok"},{"unstructured":"V. Vazirani,Approximation algorithms. Springer, Heildelberg (2001).","key":"R41"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ro.org\/10.1051\/ro:2003005\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,14]],"date-time":"2024-12-14T11:53:36Z","timestamp":1734177216000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ro.org\/10.1051\/ro:2003005"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,7]]},"references-count":41,"journal-issue":{"issue":"3"},"alternative-id":["ro2301"],"URL":"https:\/\/doi.org\/10.1051\/ro:2003005","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"1290-3868"}],"subject":[],"published":{"date-parts":[[2002,7]]}}}