Réflexion autour de nouvelles notions pour l'analyse des algorithmes d'approximation
Marc Demange,
ESSEC et
CERMSEM
Vangelis Th. Paschos,
LAMSADE, Université Paris-Dauphine
Résumé.
Nous présentons les principales caractéristiques d'un nouveau formalisme pour l'approximaion
polynomiale. Cette présentation est l'occasion d'un regard critique sur ce domaine et de
discussions sur la pertinence des notions usuelles. Elle est aussi l'occasion de se
familiariser avec l'approximation polynomiale et de comprendre ses enjeux et ses méthodes.
Cet article s'adresse donc autant aux spécialistes qu'aux non spécialistes de ce domaine.
Les différentes étapes de ce travail sont illustrées par de nombreux exemples, choisis pour
leur pertinence et leur simplicité. Nous insistons en particulier sur l'intérêt, tant
théorique qu'opérationnel, de mettre en évidence une structure au sein de la classe
NPO des problèmes d'optimisation de NP. Ainsi, nous classons les notions
d'approximation polynomiale en deux catégories. Les outils de la première permettent
d'évaluer, dans l'absolu, les propriétés d'approximation de problèmes difficiles. Les outils
de la seconde catégorie permettent de comparer, du point de vue de l'approximation,
différents problèmes : il s'agit de la notion, très fructueuse, de réduction en
approximation. Nous proposons une définition qui unifie, sous le point de vue de
l'approximation, les réductions existantes. Enfin, nous appliquons les différents concepts
pour étudier la difficulté des instances d'un problème et la structure de leur ensemble. De
nombreuses situations différentes apparaissent ainsi comme complémentaires. Cette partie
nous permet également de montrer de nouvelles directions d'études.
Mots clés :
Problèmes NP-difficiles, algorithmes d'approximation, réductions, rapport
d'approximation.
Abstract.
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. We first introduce the
key-concepts of the polynomial approximation and then we 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. The different stages of this work are accompanied by several illustrative
exemples. So, this paper is addressed to both domain researchers and non-specialist
readers. We particularly quote the great interest, both theoretical and operational, to
construct an internal structure for the class NPO (of the optimization problems
in NP). For this reason we divise the notions presented in two categories. The
tools of the former allow the individual evaluation of the approximability properties
of any NP-hard problem. The tools of the second category allow the comparison
between different problems regarding their respective approximability properties. We
find here the central complexity object, the reduction (adapted of course, in the
framework of the polynomial approximation). We propose a new definition unifying the
several approximation preserving reductions know in the litterature and also extending
their scope. The last part of the paper applies the different concepts discussed
formerly in the study of the hardness (approximation intractability) of an instance and
the apprehension of the structure of the set of hard instances of a problem. Then, many
distinct situations appear, under our point of view, as complementary ones. This part
of the paper allows us to also draw directions for further research.
Keywords :
NP-hard problems, approximation algorithms, reductions, approximation ratio.
AMS Classification :
03D15, 68Q25, 68R05.
