Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : formalisme unifié et classes d’approximation

Marc Demange; Vangelis Paschos

RAIRO - Operations Research - Recherche Opérationnelle (2002)

  • Volume: 36, Issue: 3, page 237-277
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Demange, Marc, and 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 36.3 (2002): 237-277. <http://eudml.org/doc/244839>.

@article{Demange2002,
author = {Demange, Marc, Paschos, Vangelis},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
language = {fre},
number = {3},
pages = {237-277},
publisher = {EDP-Sciences},
title = {Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : formalisme unifié et classes d’approximation},
url = {http://eudml.org/doc/244839},
volume = {36},
year = {2002},
}

TY - JOUR
AU - Demange, Marc
AU - Paschos, Vangelis
TI - Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : formalisme unifié et classes d’approximation
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2002
PB - EDP-Sciences
VL - 36
IS - 3
SP - 237
EP - 277
LA - fre
UR - http://eudml.org/doc/244839
ER -

References

top
  1. [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. Zbl0977.68539
  2. [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). Zbl0937.68002
  3. [3] C. Berge, Graphs and hypergraphs. North Holland, Amsterdam (1973). Zbl0254.05101MR357172
  4. [4] P. Berman et M. Fürer, Approximating maximum independent set in bounded degree graphs, in Proc. Symposium on Discrete Algorithms (1994) 365-371. Zbl0873.68163MR1285180
  5. [5] B.B. Boppana et M.M. Halldórsson, Approximating maximum independent sets by excluding subgraphs. BIT 32 (1992) 180-196. Zbl0761.68044MR1172185
  6. [6] V. Chvátal, A greedy-heuristic for the set covering problem. Math. Oper. Res. 4 (1979) 233-235. Zbl0443.90066MR539404
  7. [7] S.A. Cook, The complexity of theorem-proving procedures, in Proc. STOC’71 (1971) 151-158. Zbl0253.68020
  8. [8] M. Demange, P. Grisoni et V.T. Paschos, Differential approximation algorithms for some combinatorial optimization problems. Theoret. Comput. Sci. 209 (1998) 107-122. Zbl0912.68061MR1647498
  9. [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. Zbl0942.68144MR1750071
  10. [10] , Maximizing the number of unused bins. Found. Comput. Decision Sci. 26 (2001) 169-186. Zbl1204.90080MR1843945
  11. [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. Zbl0871.90069MR1388966
  12. [12] , Valeurs extrémales d’un problème d’optimisation combinatoire et approximation polynomiale. Math. Inf. Sci. Humaines 135 (1996) 51-66. Zbl0885.90093
  13. [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). Zbl1096.68783
  14. [14] , Improved approximations for maximum independent set via approximation chains. Appl. Math. Lett. 10 (1997) 105-110. Zbl0883.68067MR1457649
  15. [15] , Towards a general formal framework for polynomial approximation. LAMSADE, Université Paris-Dauphine, Cahier du LAMSADE 177 (2001). 
  16. [16] R. Duh et M. Fürer, Approximation of k -set cover by semi-local optimization, in Proc. STOC’97 (1997) 256-265. Zbl0962.68172
  17. [17] U. Feige et J. Kilian, Zero knowledge and the chromatic number, in Proc. Conference on Computational Complexity (1996) 278-287. Zbl0921.68089
  18. [18] W. Fernandez de la Vega, Sur la cardinalité maximum des couplages d’hypergraphes aléatoires uniformes. Discrete Math. 40 (1982) 315-318. Zbl0488.05051
  19. [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). Zbl0411.68039MR519066
  20. [20] M.M. Halldórsson, A still better performance guarantee for approximate graph coloring. Inform. Process. Lett. 45 (1993) 19-23. Zbl0768.68043MR1207010
  21. [21] , Approximations via partitioning. JAIST Research Report IS-RR-95-0003F, Japan Advanced Institute of Science and Technology, Japan (1995). 
  22. [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. MR1441796
  23. [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. [24] , Improved approximations of independent sets in bounded-degree graphs via subgraph removal. Nordic J. Comput. 1 (1994) 475-492. Zbl0817.68088MR1335260
  25. [25] R. Hassin et S. Lahav, Maximizing the number of unused colors in the vertex coloring problem. Inform. Process. Lett. 52 (1994) 87-90. Zbl0809.05047MR1299662
  26. [26] J. Håstad, Clique is hard to approximate within n 1 - ϵ . Acta Math. 182 (1999) 105-142. Zbl0989.68060MR1687331
  27. [27] D.S. Hochbaum, Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Appl. Math. 6 (1983) 243-254. Zbl0523.05055MR712925
  28. [28] , Approximation algorithms for NP-hard problems. PWS, Boston (1997). 
  29. [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. Zbl0345.90049MR378463
  30. [30] D.S. Johnson, Approximation algorithms for combinatorial problems. J. Comput. System Sci. 9 (1974) 256-278. Zbl0296.65036MR449012
  31. [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. MR378476
  32. [32] S. Khanna, R. Motwani, M. Sudan et U. Vazirani, On syntactic versus computational views of approximability. SIAM J. Comput. 28 (1998) 164-191. Zbl0915.68068MR1630433
  33. [33] H.R. Lewis et C.H. Papadimitriou, Elements of the theory of computation. Prentice-Hall (1981). Zbl0464.68001
  34. [34] C. Lund et M. Yannakakis, On the hardness of approximating minimization problems. J. Assoc. Comput. Mach. 41 (1994) 960-981. Zbl0814.68064MR1371491
  35. [35] R. Motwani, Lecture notes on approximation algorithms, Vol. I. Stanford University (1993). 
  36. [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. Zbl0374.90045MR503866
  37. [37] C.H. Papadimitriou et K. Steiglitz, Combinatorial optimization: Algorithms and complexity. Prentice Hall, New Jersey (1981). Zbl0503.90060MR663728
  38. [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. Zbl0963.68175
  39. [39] D. Simchi–Levi, New worst-case results for the bin-packing problem. Naval Res. Logistics 41 (1994) 579-585. Zbl0809.90111
  40. [40] P. Turán, On an extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok 48 (1941) 436-452. Zbl0026.26903
  41. [41] V. Vazirani, Approximation algorithms. Springer, Heildelberg (2001). Zbl1005.68002MR1851303

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.