Article contents
Autour de nouvelles notions pour l'analyse desalgorithmes d'approximation : formalisme unifié et classes d'approximation
Published online by Cambridge University Press: 15 April 2003
Abstract
Cet article est le premier d'une série de deux articles oùnous présentons les principales caractéristiques d'un nouveauformalisme pour l'approximation polynomiale (algorithmiquepolynomiale à garanties de performances pour les problèmesNP-difficiles). Ce travail est l'occasion d'unregard critique sur ce domaine et de discussions sur la pertinencedes notions usuelles. Il est aussi l'occasion de se familiariseravec l'approximation polynomiale, de comprendre ses enjeux etses méthodes. Ces deux articles s'adressent donc autant auxspécialistes qu'aux non spécialistes de ce domaine. Nous insistons toutparticulièrementsur l'intérêt, tant théorique qu'opérationnel, de mettre enévidence une structure au sein de la classe NPO desproblèmes d'optimisation de NP. Dans ce premier article, nousnous intéressons aux outils qui permettent d'évaluer,dans l'absolu, les propriétés d'approximation de problèmesdifficiles. Nous discutons notamment les notions de chaînesd'approximation, de niveau d'approximation, d'ordre de difficultéainsi que deux notions de limites (par rapport à une suited'algorithmes et par rapport aux instances). Chaque notion estlargement discutée et illustrée par de nombreux exempleschoisis essentiellement pour leur valeur pédagogique. Mots Clés. Complexité, difficulté intrinsèque, analyse des algorithmes et des problèmes,algorithmes d'approximation. Classification Mathématique. 68Q15, 68Q17, 68Q25, 68W25.
- Type
- Research Article
- Information
- Copyright
- © EDP Sciences, 2002
References
- 2
- Cited by