Applications théoriques pour les algorithmes d'approximation

Dernièrement, j'ai commencé à chercher des algorithmes d'approximation pour les problèmes NP-difficiles et je me demandais les raisons théoriques de les étudier. (La question n'est pas censée être incendiaire - je suis simplement curieux).

Une théorie vraiment belle est sortie de l'étude des algorithmes d'approximation - la connexion entre le théorème PCP et la dureté de l'approximation, la conjecture UGC, l'algorithme d'approximation de Goeman-Williamson, etc.

Je me posais des questions sur l'intérêt d'étudier des algorithmes d'approximation pour des problèmes comme Travelling Salesman, Asymmetric Traveling Salesman et d'autres variantes, divers problèmes de conception de mécanismes (par exemple dans les enchères combinatoires), etc. Ces algorithmes d'approximation ont-ils été utiles dans d'autres parties de la théorie dans le passé ou sont-ils étudiés uniquement pour eux-mêmes?

Remarque: je ne pose aucune question sur les applications pratiques car, pour autant que je sache, dans le monde réel, ce sont principalement des heuristiques qui sont appliquées plutôt que des algorithmes d'approximation et les heuristiques sont rarement informées par les informations obtenues en étudiant les algorithmes d'approximation pour le problème.

Je suis fortement en désaccord avec le dernier paragraphe. De telles déclarations générales ne sont pas utiles. Si vous regardez des articles dans de nombreux domaines des systèmes tels que les réseaux, les bases de données, l'IA, etc., vous verrez que de nombreux algorithmes d'approximation sont utilisés dans la pratique. Il y a des problèmes pour lesquels on désire des réponses très précises; disons par exemple une compagnie aérienne intéressée à optimiser la programmation de sa flotte. Dans de tels cas, les gens utilisent diverses heuristiques qui prennent beaucoup de temps de calcul mais obtiennent de meilleurs résultats qu'un algorithme d'approximation générique ne peut donner.

Maintenant, pour quelques raisons théoriques d'étudier les algorithmes d'approximation. Tout d'abord, qu'est-ce qui explique le fait que le sac à dos est très facile en pratique alors que la coloration des graphiques est assez difficile? Les deux sont NP-Hard et poly-temps réductibles l'un à l'autre. Deuxièmement, en étudiant des algorithmes d'approximation pour des cas particuliers d'un problème, on peut déterminer quelles classes d'instances sont susceptibles d'être faciles ou difficiles. Par exemple, nous savons que de nombreux problèmes admettent un PTAS dans les graphes planaires et sans mineur alors qu'ils sont beaucoup plus difficiles dans les graphes généraux arbitraires. L'idée d'approximation imprègne la conception d'algorithmes modernes. Par exemple, les gens utilisent des algorithmes de streaming de données et sans la lentille d'approximation, il est difficile de comprendre / concevoir des algorithmes car même des problèmes simples ne peuvent pas être résolus exactement.

Le comptage approximatif est utile dans la théorie de la complexité. Par exemple, Jin Cai l'utilise pour montrer que , voir http://pages.cs.wisc.edu/~jyc/papers/S2-j.pdf$S_2^p \subseteq ZPP^{NP}$

Je suis également en désaccord avec la "note", du moins énoncée dans cette généralité. À ce sujet, quelqu'un sait-il si la conférence Kanellakis Award de David Johnson est disponible quelque part?

De plus, une fois que nous réalisons que tous les problèmes NP-difficiles sont équivalents par rapport à la complexité la plus défavorable des solutions exactes, il est très naturel de se renseigner sur la complexité de la recherche de solutions approximatives. Et Chandra fait un grand point sur le changement de perspective que les algorithmes d'approximation apportent à la conception d'algorithmes.

$O(\log n)$

Les meilleures heuristiques sont vraiment des algorithmes d'approximation. Les plus beaux algorithmes d'approximation ne sont que des heuristiques "stupides" qui fonctionnent. Par exemple, recherche locale de clustering, clustering gourmand (Gonzalez), un pour le prix de deux, divers algorithmes gourmands, etc., etc., etc.

L'étude des algorithmes d'approximation consiste donc vraiment à comprendre quelles heuristiques sont des algorithmes d'approximation garantis. L'espoir est que la recherche sur les algorithmes d'approximation crée deux types de fertilisation croisée:

• Transformez des idées qui fonctionnent de l'heuristique en outils de conception d'algorithmes. De même, déplacez les idées de la conception d'algorithmes vers des heuristiques / algorithmes qui fonctionnent bien dans la pratique.
• fécondation croisée entre une personne qui vient d'obtenir son diplôme et un poste.

En bref, le monde n'est pas exact, les entrées ne sont pas exactes, les fonctions cibles optimisées par divers problèmes d'algorithmes ne sont pas exactes et au mieux représentent une approximation floue de ce que l'on veut, et les calculs ne sont pas exacts. Pourquoi quelqu'un apprendrait-il des algorithmes exacts? (Réponse: Parce que les algorithmes exacts ne sont que de très bons algorithmes d'approximation.)

Dans le monde réel, il y a très peu d'algorithmes exacts - vous devez utiliser l'approximation pour être pertinent à distance ...

Traiter des problèmes avec des variables continues est très ennuyeux avec des algorithmes exacts. Par exemple, que signifie spécifier les poids de contour d'une instance TSP avec des nombres réels exacts?

Lorsque nous autorisons les algorithmes FPTAS pour ces problèmes, nous pouvons quantifier ces paramètres en nombres entiers. Cela rend le problème beaucoup plus efficace (peut utiliser des machines Turing standard), mais entraîne une petite erreur.