Approximating values and solutions of NP-optimization problems : concepts and examples
Marc Demange,
CERMSEM
José Lorenzo,
CERMSEM
Résumé.
Nous proposons un cadre formel permettant de différencier l'étude d'algorithmes polynomiaux
constructifs (fournissant des solutions) pour l'approximation de problèmes d'optimisation NP (NPO) de
celle d'algorithmes non-constructifs (en valeur). Nous introduisons une nouvelle classe, notée SubNPO
(sous-problèmes de NPO), contenant NPO ainsi que d'autres problèmes utilisés dans de
récents travaux. Pour cette classe, nous définissons deux types d'algorithmes d'approximation : les
constructifs et les non-constructifs. Dans chaque cas, nous étendons les notions de niveau
d'approximation, de réduction en approximation et des complétudes associées. Nous proposons
alors, sous une hypothèse de complétude, un résultat d'équivalence entre
l'approximation constructive et l'approximation non-constructive. Ceci généralise au cas de
l'approximation polynomiale un célèbre résultat de A. Paz et S. Moran. Enfin, nous mettons
en évidence des exemples où les deux points de vue diffèrent. Nous montrons notamment que
plusieurs problèmes connus pour être complets dans le cadre de l'approximation polynomiale
constructive ne le sont pas dans celui de l'approximation polynomiale non-constructive.
Mots clés :
Complexité algorithmique, algoritmes d'approximation, solutions approchées et valeurs approchées.
Abstract.
We shape a formal framework for distinguishing the behaviour of constructive and non-constructive polynomial time
approximation algorithms for NP optimization problems. We introduce a new class, called SubNPO (sub-problems of
NPO), that includes NPO and also some other problems used in recent works. For this class, we define two types of
approximation algorithms : the constructive ones and the non-constructive ones. For both cases we extend the
notions of approximation level, of approximated preserving reductions and of related completeness. Then, we
devise, under a completeness hypothesis, an equivalence result between constructive approximation and the
non-constructive one. It generalizes, to the case of polynomial time approximation, a famous result of A. Paz and
S. Moran. We finally point out some cases where both points of view differ from each other. In particular, we
show that several problems, known to be complete for polynomial time constructive approximation, are not complete
for the non-constructive one.
Keywords :
Computational complexity, approximation algorithms, approximated solutions and approximated values.
AMS Classification :
03D15, 68Q25, 68R10.
