Voir la notice de l'article provenant de la source Numdam
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},
pages = {237--277},
publisher = {EDP-Sciences},
volume = {36},
number = {3},
year = {2002},
doi = {10.1051/ro:2003005},
zbl = {1089.68668},
mrnumber = {1988279},
language = {fr},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro:2003005/}
}
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 SP - 237 EP - 277 VL - 36 IS - 3 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro:2003005/ DO - 10.1051/ro:2003005 LA - fr ID - RO_2002__36_3_237_0 ER -
%0 Journal Article %A Demange, Marc %A Paschos, Vangelis %T Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation %J RAIRO - Operations Research - Recherche Opérationnelle %D 2002 %P 237-277 %V 36 %N 3 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro:2003005/ %R 10.1051/ro:2003005 %G fr %F 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, Tome 36 (2002) no. 3, pp. 237-277. doi: 10.1051/ro:2003005
Cité par Sources :