Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation
RAIRO - Operations Research - Recherche Opérationnelle, Volume 36 (2002) no. 3, p. 237-277

The main objective of the polynomial approximation is the development of polynomial time algorithms for NP-hard problems, these algorithms guaranteeing feasible solutions lying “as near as possible” to the optimal ones. This work is the fist part of a couple of papers where we introduce the key-concepts of the polynomial approximation and present the main lines of a new formalism. Our purposes are, on the one hand, to present this theory and its objectives and, on the other hand, to discuss the appropriateness and the pertinence of its constitutive elements, as people knew them until now, and to propose their enrichment. Henceforth, these papers are addressed to both domain researchers and non-specialist readers. We particularly quote the great theoretical and operational interest in constructing an internal structure for the class NPO (of the optimization problems in NP). In this fist part, we focus on some basic tools allowing the individual evaluation of the approximability properties of any NP-hard problem. We present and discuss notions as algorithmic chain, approximation level, hardness threshold and two notions of limits (with respect to algorithmic chains and with respect to problems instances). The notions dealt in the paper are presented together with several illustrative examples.

@article{RO_2002__36_3_237_0,
author = {Demange, Marc and Paschos, Vangelis},
title = {Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifi\'e et classes d'approximation},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
publisher = {EDP-Sciences},
volume = {36},
number = {3},
year = {2002},
pages = {237-277},
doi = {10.1051/ro:2003005},
mrnumber = {1988279},
zbl = {1089.68668},
language = {fr},
url = {http://www.numdam.org/item/RO_2002__36_3_237_0}
}

Demange, Marc; Paschos, Vangelis. Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation. RAIRO - Operations Research - Recherche Opérationnelle, Volume 36 (2002) no. 3, pp. 237-277. doi : 10.1051/ro:2003005. http://www.numdam.org/item/RO_2002__36_3_237_0/

[1] S. Arora, C. Lund, R. Motwani, M. Sudan et M. Szegedy, Proof verification and intractability of approximation problems, in Proc. FOCS'92 (1992) 14-23. | Zbl 0977.68539

[2] 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). | Zbl 0937.68002

[3] C. Berge, Graphs and hypergraphs. North Holland, Amsterdam (1973). | MR 357172 | Zbl 0254.05101

[4] P. Berman et M. Fürer, Approximating maximum independent set in bounded degree graphs, in Proc. Symposium on Discrete Algorithms (1994) 365-371. | MR 1285180 | Zbl 0873.68163

[5] B.B. Boppana et M.M. Halldórsson, Approximating maximum independent sets by excluding subgraphs. BIT 32 (1992) 180-196. | MR 1172185 | Zbl 0761.68044

[6] V. Chvátal, A greedy-heuristic for the set covering problem. Math. Oper. Res. 4 (1979) 233-235. | MR 539404 | Zbl 0443.90066

[7] S.A. Cook, The complexity of theorem-proving procedures, in Proc. STOC'71 (1971) 151-158. | Zbl 0253.68020

[8] M. Demange, P. Grisoni et V.T. Paschos, Differential approximation algorithms for some combinatorial optimization problems. Theoret. Comput. Sci. 209 (1998) 107-122. | MR 1647498 | Zbl 0912.68061

[9] M. Demange, J. Monnot et V.T. Paschos, Bridging gap between standard and differential polynomial approximation: The case of bin-packing. Appl. Math. Lett. 12 (1999) 127-133. | MR 1750071 | Zbl 0942.68144

[10] , Maximizing the number of unused bins. Found. Comput. Decision Sci. 26 (2001) 169-186. | MR 1843945

[11] M. Demange et V.T. Paschos, On an approximation measure founded on the links between optimization and polynomial approximation theory. Theoret. Comput. Sci. 158 (1996) 117-141. | MR 1388966 | Zbl 0871.90069

[12] , Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale. Math. Inf. Sci. Humaines 135 (1996) 51-66. | Numdam | Zbl 0885.90093

[13] , Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances. RAIRO: Oper. Res. (à paraître). | Numdam | Zbl 1096.68783

[14] , Improved approximations for maximum independent set via approximation chains. Appl. Math. Lett. 10 (1997) 105-110. | MR 1457649 | Zbl 0883.68067

[15] , Towards a general formal framework for polynomial approximation. LAMSADE, Université Paris-Dauphine, Cahier du LAMSADE 177 (2001).

[16] R. Duh et M. Fürer, Approximation of $k$-set cover by semi-local optimization, in Proc. STOC'97 (1997) 256-265. | Zbl 0962.68172

[17] U. Feige et J. Kilian, Zero knowledge and the chromatic number, in Proc. Conference on Computational Complexity (1996) 278-287.

[18] W. Fernandez De La Vega, Sur la cardinalité maximum des couplages d'hypergraphes aléatoires uniformes. Discrete Math. 40 (1982) 315-318. | Zbl 0488.05051

[19] M.R. Garey et D.S. Johnson, Computers and intractability. A guide sto the theory of NP-completeness. W.H. Freeman, San Francisco (1979). | MR 519066 | Zbl 0411.68039

[20] M.M. Halldórsson, A still better performance guarantee for approximate graph coloring. Inform. Process. Lett. 45 (1993) 19-23. | MR 1207010 | Zbl 0768.68043

[21] , Approximations via partitioning. JAIST Research Report IS-RR-95-0003F, Japan Advanced Institute of Science and Technology, Japan (1995).

[22] , Approximating $k$-set cover and complementary graph coloring, in Proc. International Integer Programming and Combinatorial Optimization Conference. Springer Verlag, Lecture Notes in Comput. Sci. 1084 (1996) 118-131. | MR 1441796

[23] M.M. Halldórsson et J. Radhakrishnan, Greed is good: Approximating independent sets in sparse and bounded-degree graphs, in Proc. STOC'94 (1994) 439-448.

[24] , Improved approximations of independent sets in bounded-degree graphs via subgraph removal. Nordic J. Comput. 1 (1994) 475-492. | MR 1335260 | Zbl 0817.68088

[25] R. Hassin et S. Lahav, Maximizing the number of unused colors in the vertex coloring problem. Inform. Process. Lett. 52 (1994) 87-90. | MR 1299662 | Zbl 0809.05047

[26] J. Håstad, Clique is hard to approximate within ${n}^{1-ϵ}$. Acta Math. 182 (1999) 105-142. | MR 1687331 | Zbl 0989.68060

[27] D.S. Hochbaum, Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Appl. Math. 6 (1983) 243-254. | MR 712925 | Zbl 0523.05055

[28] , Approximation algorithms for NP-hard problems. PWS, Boston (1997).

[29] O.H. Ibarra et C.E. Kim, Fast approximation algorithms for the knapsack and sum of subset problems. J. Assoc. Comput. Mach. 22 (1975) 463-468. | MR 378463 | Zbl 0345.90049

[30] D.S. Johnson, Approximation algorithms for combinatorial problems. J. Comput. System Sci. 9 (1974) 256-278. | MR 449012 | Zbl 0296.65036

[31] R.M. Karp, Reducibility among combinatorial problems, dans Complexity of computer computations, édité par R.E. Miller et J.W. Thatcher. Plenum Press, New York (1972) 85-103. | MR 378476

[32] S. Khanna, R. Motwani, M. Sudan et U. Vazirani, On syntactic versus computational views of approximability. SIAM J. Comput. 28 (1998) 164-191. | MR 1630433 | Zbl 0915.68068

[33] H.R. Lewis et C.H. Papadimitriou, Elements of the theory of computation. Prentice-Hall (1981). | Zbl 0464.68001

[34] C. Lund et M. Yannakakis, On the hardness of approximating minimization problems. J. Assoc. Comput. Mach. 41 (1994) 960-981. | MR 1371491 | Zbl 0814.68064

[35] R. Motwani, Lecture notes on approximation algorithms, Vol. I. Stanford University (1993).

[36] G.L. Nemhauser, L.A. Wolsey et M.L. Fischer, An analysis of approximations for maximizing submodular set functions. Math. Programming 14 (1978) 265-294. | MR 503866 | Zbl 0374.90045

[37] C.H. Papadimitriou et K. Steiglitz, Combinatorial optimization: Algorithms and complexity. Prentice Hall, New Jersey (1981). | MR 663728 | Zbl 0503.90060

[38] R. Raz et S. Safra, A sub-constant error probability low-degree test and a sub-constant error probability PCP characterization of NP, in Proc. STOC'97 (1997) 475-484. | Zbl 0963.68175

[39] D. Simchi-Levi, New worst-case results for the bin-packing problem. Naval Res. Logistics 41 (1994) 579-585. | Zbl 0809.90111

[40] P. Turán, On an extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok 48 (1941) 436-452. | Zbl 0026.26903

[41] V. Vazirani, Approximation algorithms. Springer, Heildelberg (2001). | MR 1851303 | Zbl 1005.68002