Cadre : optimisation combinatoire - approximation polynomiale au pire des cas des problèmes NP-difficiles - classes d'approximation. Cet ouvrage confronte la problématique de la recherche locale à l'approximation au pire des cas ; précisément, il restreint l'ensemble des solutions approchées envisagées aux seuls optima locaux et pose alors la question suivante : "quels sont les problèmes dont tous les optima locaux sont des bonnes solutions ?" Les réponses sont proposées tant en classique qu'en différentiel, cadre d'analyse malheureusement encore sous-représenté dans la littérature scientifique. En différentiel, on cherche tout autant à s'éloigner de la pire solution qu'à se rapprocher de l'optimum, tandis que le cadre classique compare la solution approchée à la seule valeur optimale. Ce livre possède une dimension pédagogique par la diversité des démarches entreprises et des outils utilisés (notamment, l'outil clé de réduction), par la façon dont ceux-ci sont exprimés, également par un chapitre qui retrace et définit les concepts essentiels de l'approximation polynomiale.
Publié le : 2002-07-05
Classification:
approximation polynomiale,
recherche locale,
rapport différentiel,
GLO,
[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC],
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC],
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
@article{hal-00003255,
author = {Toulouse, Sophie and Monnot, J\'er\^ome and Paschos, Vangelis},
title = {Approximation polynomiale des probl\`emes NP-difficiles - Optima locaux et rapport diff\'erentiel},
journal = {HAL},
volume = {2002},
number = {0},
year = {2002},
language = {fr},
url = {http://dml.mathdoc.fr/item/hal-00003255}
}
Toulouse, Sophie; Monnot, Jérôme; Paschos, Vangelis. Approximation polynomiale des problèmes NP-difficiles - Optima locaux et rapport différentiel. HAL, Tome 2002 (2002) no. 0, . http://gdmltest.u-ga.fr/item/hal-00003255/