Algorithmes d'approximation

Les algorithmes d'approximation résolvent des problèmes d'optimisation NP-difficiles en temps polynomial tout en garantissant une solution dont la qualité est prouvablement à un facteur fixe de l'optimum, offrant ainsi des compromis rigoureux entre la qualité de la solution et la tractabilité.

Definition

Un algorithme d'approximation pour un problème d'optimisation est un algorithme en temps polynomial qui fournit une solution réalisable dont la valeur objective est garantie d'être à l'intérieur d'un facteur multiplicatif prouvé — le ratio d'approximation — de la valeur optimale.

Scope

Ce sujet aborde les algorithmes en temps polynomial qui fournissent des solutions quasi-optimales à des problèmes d'optimisation difficiles, le ratio d'approximation qui mesure leur qualité, et les principales techniques de conception : les heuristiques gloutonnes (greedy) et de recherche locale (local-search) avec des bornes prouvables, la relaxation et l'arrondi de programmes linéaires, et la méthode primale-duale. Il couvre également les schémas d'approximation (PTAS et FPTAS) et l'existence de résultats d'inapproximabilité qui limitent la qualité d'approximation de certains problèmes.

Core questions

• Comment la qualité d'une solution approximative est-elle mesurée par un ratio d'approximation ?
• Comment la relaxation et l'arrondi de programmes linéaires transforment-ils un optimum fractionnaire en une solution entière bornée ?
• Comment les méthodes gloutonnes (greedy) et de recherche locale (local-search) fournissent-elles des garanties d'approximation prouvables ?
• Que sont les schémas d'approximation en temps polynomial, et quels problèmes les admettent ?
• Pourquoi certains problèmes peuvent-ils être approximés arbitrairement bien tandis que d'autres ne peuvent pas être approximés du tout ?

Key concepts

• ratio d'approximation
• optimisation NP-difficile
• approximation gloutonne (greedy)
• recherche locale (local search)
• relaxation et arrondi de programmes linéaires
• méthode primale-duale
• PTAS et FPTAS
• inapproximabilité

Key theories

Ratio d'approximation

Le ratio d'approximation borne l'écart maximal entre la solution d'un algorithme et l'optimum dans le pire des cas ; une c-approximation garantit une solution à un facteur c de l'optimum, fournissant un certificat de qualité rigoureux pour un algorithme efficace.

Relaxation et arrondi de programmes linéaires

De nombreux algorithmes d'approximation relaxent un programme en nombres entiers en un programme linéaire, le résolvent efficacement, et arrondissent la solution fractionnaire en une solution entière tout en bornant la perte, produisant des ratios prouvables via les cadres primal-dual ou d'arrondi.

Clinical relevance

Les algorithmes d'approximation rendent l'optimisation intraitable utilisable en pratique : les méthodes à ratio borné pour la couverture d'ensemble (set cover), la couverture de sommets (vertex cover), la localisation d'installations (facility location), l'ordonnancement (scheduling) et le problème du voyageur de commerce (traveling salesman problem) guident des systèmes réels en logistique, conception de réseaux et recherche opérationnelle, fournissant des solutions avec des garanties de qualité plutôt que des heuristiques non vérifiées.

History

Le domaine a émergé dans les années 1970, avec l'analyse par Johnson des ratios d'approximation pour des problèmes tels que la couverture d'ensemble (set cover) et le problème du rangement de bacs (bin packing), et l'algorithme de Christofides de 1976 pour le problème du voyageur de commerce métrique (metric traveling salesman problem). Les techniques de programmation linéaire et primale-duale ont mûri dans les années 1980 et 1990, et les preuves vérifiables de manière probabiliste (probabilistically checkable proofs) ont ensuite établi de solides résultats d'inapproximabilité, le tout consolidé dans les manuels de Vazirani et de Williamson et Shmoys.

Key figures

• Vijay Vazirani
• David Williamson
• David Shmoys
• David Johnson
• László Lovász

Seminal works

• vazirani2001
• williamson2011
• cormen2009

Frequently asked questions

Que garantit un algorithme de 2-approximation ?

Pour un problème de minimisation, une 2-approximation retourne toujours une solution dont le coût est au plus le double du coût optimal (et au moins optimal pour un problème de maximisation, à un facteur d'un demi près). La garantie est valable pour chaque entrée, quelle que soit sa nature adversaire.

Tout problème NP-difficile peut-il être bien approximé ?

Non. Certains problèmes admettent des schémas d'approximation qui s'approchent arbitrairement de l'optimum, d'autres ont un ratio constant optimal, et certains ne peuvent pas être approximés à l'intérieur d'un facteur raisonnable, à moins que P ne soit égal à NP. Les résultats d'inapproximabilité établissent formellement ces limites.