Algorithme d'approximation

En informatique théorique, un algorithme d'approximation est une méthode permettant de calculer une solution approchée à un problème algorithmique d'optimisation. Plus précisément, c'est une heuristique garantissant à la qualité de la solution qui fournit un rapport inférieur (si l'on minimise) à une constante, par rapport à la qualité optimale d'une solution, pour toutes les instances possibles du problème.

L'intérêt de tels algorithmes est qu'il est parfois plus facile de trouver une solution approchée qu'une solution exacte, le problème pouvant par exemple être NP-complet mais admettre un algorithme d'approximation polynomial. Ainsi, dans les situations où l'on cherche une bonne solution, mais pas forcément la meilleure, un algorithme d'approximation peut être un bon outil.

Définitions[modifier | modifier le code]

Approximation[modifier | modifier le code]

Selon la nature du problème (maximisation, minimisation, etc.) la définition peut varier, on donne ici la définition classique pour un problème de minimisation avec facteur d'approximation constant.

Pour un problème de minimisation ayant une solution optimale de valeur $z^{*}$ , un algorithme d'approximation de facteur $\rho >1$ (i.e. un algorithme $\rho$ -approché) est un algorithme donnant une solution de valeur $z$ , avec la garantie que $z\leq \rho z^{*}$ .

Schéma d'approximation[modifier | modifier le code]

Un schéma d'approximation est un algorithme prenant comme entrée les données du problèmes mais aussi une valeur $\epsilon >0$ et calculant une solution approchée avec un facteur $(1+\epsilon )$ . Si le temps de calcul est polynomial en la taille de l'entrée pour chaque valeur $\epsilon$ , on parle de schéma d'approximation en temps polynomial (abrégé PTAS en anglais). Si de plus, on demande que le temps de calcul soit aussi en $1/\epsilon$ , on parle de schéma d'approximation en temps entièrement polynomial (abrégé FPTAS en anglais)^[1].

Exemple[modifier | modifier le code]

Par exemple pour le problème du transversal minimum puisque tout transversal formé par les sommets incidents aux arêtes d'un couplage maximal pour l'inclusion a une cardinalité inférieure à deux fois l'optimum.

C'est aussi le cas pour le cas particulier du voyageur de commerce où les poids satisfont les inégalités triangulaires car alors, le poids minimum d'un arbre couvrant est toujours inférieur à deux fois l'optimum. En affinant cette approche en utilisant un couplage bien choisi on peut aussi obtenir un facteur d'approximation de 3/2, avec l'algorithme de Christofides.

Techniques algorithmiques[modifier | modifier le code]

Parmi les techniques utilisées^[2], on compte les méthodes d'algorithmique classique, par exemple un algorithme glouton permet parfois d'obtenir une bonne approximation à défaut de calculer une solution optimale. On peut aussi citer des algorithmes de recherche locale et de programmation dynamique.

Beaucoup d'algorithmes sont basées sur l'optimisation linéaire. On peut par exemple arrondir une solution fractionnaire ou utiliser un schéma primal-dual. Une technique plus avancée est d'utiliser l'optimisation SDP, comme pour le problème de la coupe maximum.

Difficulté d'approximation[modifier | modifier le code]

Parmi les problèmes NP-complets certains sont dits difficile à approximer, c'est-à-dire qu'ils n'admettent pas d'algorithme d'approximation si l'on suppose certaines hypothèses, par exemple P différent de NP ou bien la conjecture des jeux uniques.

Exemples simples[modifier | modifier le code]

Le problème du voyageur de commerce dans un graphe $G=(V,E)$ avec des poids quelconques (positifs) est un problème qui n'admet pas d'algorithme d'approximation. En effet, tout algorithme d'approximation pour ce problème dans le graphe complet $K_{V}$ où les arêtes de $E$ ont une valeur nulle et les autres la valeur 1 fournit une réponse au problème de décision NP-complet de statuer sur l'hamiltonicité d'un graphe (en l'occurrence $G$ est hamiltonien si et seulement si l'algorithme approché fournit une solution de valeur nulle).

Un autre problème est le problème du k-centre métrique qui admet une réduction simple au problème de l'ensemble dominant^[3].

Techniques avancées[modifier | modifier le code]

Il existe des techniques plus complexes pour montrer des résultats de difficulté d'approximation. Elles tournent essentiellement autour du théorème PCP. Plus récemment la conjecture des jeux uniques a été utilisée pour montrer des résultats plus forts.

Historique[modifier | modifier le code]

Des algorithmes d'approximation ont été découverts avant même la mise en place de la théorie de la NP-complétude^[4], par exemple par Paul Erdős dans les années 1960, pour le problème de la coupe maximum^[5] ou Ronald Graham, pour les algorithmes d'ordonnancement ^[6]^,^[7] . Cependant c'est à la suite de cette théorie que le domaine s'est vraiment développé^[4]. L'utilisation de l'optimisation linéaire est due à László Lovász dans les années 1970^[4], pour le problème de couverture par ensembles^[8].

Dans les années 1990, le théorème PCP a été une avancée très importante pour la non-approximabilité.

Notes et références[modifier | modifier le code]

↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, 2002 [détail de l’édition], chap. 35.
↑ David P. Williamson et David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press (lire en ligne)
↑ Voir (en) Vijay Vazirani, Approximation algorithms, Springer Verlag, 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), chap. 5 (« k-center »)
↑ ^{a b et c} (en) Vijay Vazirani, Approximation algorithms, Springer Verlag, 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), chap. 1.4 (« Introduction : Notes ») p. 10.
↑ Paul Erdős, « Gráfok páros körüljárású részgráfjairól (On bipartite subgraphs of graphs, in Hungarian), », Mat. Lapok, vol. 18,‎ 1967, p. 283-288
↑ R. L. Graham, « Bounds for certain multiprocessing anomalies », Bell System Technical Journal, vol. 45, n^o 9,‎ 1966, p. 1563–1581 (DOI 10.1002/j.1538-7305.1966.tb01709.x, lire en ligne)
↑ R. L. Graham, « Bounds on multiprocessing timing anomalies », SIAM Journal on Applied Mathematics, vol. 17,‎ 1969, p. 416–429 (DOI 10.1137/0117039, MR 249214, lire en ligne)
↑ László Lovász, « On the ratio of optimal integral and fractional covers », Discrete mathematics, vol. 13, n^o 4,‎ 1975, p. 383-390

Portail de l'informatique théorique

[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, 2002 [détail de l’édition], chap. 35.

[2] David P. Williamson et David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press (lire en ligne)

[3] Voir (en) Vijay Vazirani, Approximation algorithms, Springer Verlag, 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), chap. 5 (« k-center »)

[vazirani-4] {a b et c} (en) Vijay Vazirani, Approximation algorithms, Springer Verlag, 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), chap. 1.4 (« Introduction : Notes ») p. 10.

[5] Paul Erdős, « Gráfok páros körüljárású részgráfjairól (On bipartite subgraphs of graphs, in Hungarian), », Mat. Lapok, vol. 18,‎ 1967, p. 283-288

[6] R. L. Graham, « Bounds for certain multiprocessing anomalies », Bell System Technical Journal, vol. 45, n^o 9,‎ 1966, p. 1563–1581 (DOI 10.1002/j.1538-7305.1966.tb01709.x, lire en ligne)

[7] R. L. Graham, « Bounds on multiprocessing timing anomalies », SIAM Journal on Applied Mathematics, vol. 17,‎ 1969, p. 416–429 (DOI 10.1137/0117039, MR 249214, lire en ligne)

[8] László Lovász, « On the ratio of optimal integral and fractional covers », Discrete mathematics, vol. 13, n^o 4,‎ 1975, p. 383-390

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]