« c’est un résultat que j’ai voulu toute ma carrière”, a déclaré David Williamson de L’Université Cornell, qui étudie le problème des vendeurs itinérants depuis les années 1980.
le problème des vendeurs itinérants est l’un des rares problèmes fondamentaux auxquels les informaticiens théoriques se tournent encore et encore pour tester les limites d’un calcul efficace. Le nouveau résultat » est la première étape pour montrer que les frontières du calcul efficace sont en fait meilleures que ce que nous pensions”, a déclaré Williamson.,
progression fractionnaire
bien qu’il n’y ait probablement pas de méthode efficace qui trouve toujours le trajet le plus court, il est possible de trouver quelque chose de presque aussi bon: l’arbre le plus court reliant toutes les villes, c’est-à-dire un réseau de connexions (ou « bords”) sans boucles fermées. L’algorithme de Christofides utilise cet arbre comme colonne vertébrale pour un tour aller-retour, en ajoutant des bords supplémentaires pour le convertir en un aller-retour.
Tout itinéraire aller-retour doit avoir un nombre pair d’arêtes dans chaque ville, car chaque arrivée est suivie d’un départ., Il s’avère que l’inverse est également vrai — si chaque ville d’un réseau a un nombre pair de connexions, les bords du réseau doivent tracer un aller-retour.
l’arbre le plus court reliant toutes les villes n’a pas cette propriété de régularité, car toute ville à la fin d’une branche n’a qu’une seule connexion à une autre ville. Donc, pour transformer L’arbre le plus court en un aller-retour, Christofides (décédé l’année dernière) a trouvé le meilleur moyen de connecter des paires de villes qui ont un nombre impair de bords. Ensuite, il a prouvé que l’aller-retour résultant ne sera jamais plus de 50% plus long que le meilleur aller-retour possible.,
ce faisant, il a peut — être conçu l’algorithme d’approximation le plus célèbre en informatique théorique-celui qui constitue généralement le premier exemple dans les manuels et les cours.
« Tout le monde connaît l’algorithme simple”, a déclaré Alantha Newman de L’Université Grenoble Alpes et du Centre national de la Recherche Scientifique en France. Et quand vous le savez, elle a dit : » vous connaissez l’état de l’art” — du moins, vous l’avez fait jusqu’en juillet dernier.
les informaticiens soupçonnent depuis longtemps qu’il devrait y avoir un algorithme d’approximation qui surpasse l’algorithme de Christofides., Après tout, son algorithme simple et intuitif n’est pas toujours un moyen aussi efficace de concevoir un itinéraire de vendeur itinérant, car l’arbre le plus court reliant les villes n’est peut-être pas le meilleur épine dorsale que vous puissiez choisir. Par exemple, si cet arbre a de nombreuses branches, chaque ville à la fin d’une branche devra être jumelée à une autre ville, ce qui pourrait former de nombreuses nouvelles connexions coûteuses.,
en 2010, Oveis Gharan, Saberi et Mohit Singh du Georgia Institute of Technology ont commencé à se demander s’il serait possible d’améliorer L’algorithme de Christofides En choisissant non pas l’arbre le plus court reliant toutes les villes, mais un arbre aléatoire d’une collection soigneusement choisie. Ils se sont inspirés d’une version alternative du problème du vendeur itinérant dans lequel vous êtes autorisé à voyager le long d’une combinaison de chemins — peut-être que vous arrivez à Denver via 3/4 de la route de Chicago à Denver plus 1/4 de la route de Los Angeles à Denver.,
contrairement au problème du vendeur itinérant régulier, ce problème fractionnaire peut être résolu efficacement. Et tandis que les itinéraires fractionnaires n’ont pas de sens physique, les informaticiens ont longtemps cru que le meilleur itinéraire fractionnaire devrait être un guide approximatif des contours de bonnes routes ordinaires.
donc, pour créer leur algorithme, Oveis Gharan, Saberi et Singh ont défini un processus aléatoire qui choisit un arbre reliant toutes les villes, de sorte que la probabilité qu’un bord donné soit dans l’arbre est égale à la fraction de ce bord dans la meilleure route fractionnaire., Il existe de nombreux processus aléatoires de ce type, de sorte que les chercheurs en ont choisi un qui a tendance à produire des arbres avec de nombreuses villes uniformément connectées. Après que ce processus aléatoire crache un arbre spécifique, leur algorithme le branche dans le schéma de Christofides pour faire correspondre les villes avec un nombre impair d’arêtes, pour le convertir en un aller-retour.
Cette méthode semble prometteuse, non seulement pour les trois chercheurs, mais à d’autres scientifiques de l’informatique. ” L’intuition est simple », a déclaré Ola Svensson de L’Ecole Polytechnique Fédérale de Lausanne. Mais « pour prouver qu’il s’avère être une bête différente., »
L’année suivante, cependant, Oveis Gharan, Saberi et Singh ont réussi à prouver que leur algorithme Bat celui de Christofides pour les problèmes de vendeurs itinérants” graphiques » — ceux où les distances entre les villes sont représentées par un réseau (n’incluant pas nécessairement toutes les connexions) dans lequel chaque bord a la même longueur. Mais les chercheurs n’ont pas pu comprendre comment étendre leur résultat au problème général des vendeurs itinérants, dans lequel certains bords peuvent être beaucoup plus longs que d’autres.,
« Si nous devons ajouter un bord super cher à la correspondance, nous sommes foutus, en gros”, a déclaré Karlin.
repoussant
néanmoins, Oveis Gharan est sorti de cette collaboration avec une conviction inébranlable que leur algorithme devrait battre l’algorithme de Christofides pour le problème général des vendeurs itinérants. « Je n’ai jamais eu un doute,” dit-il.
Oveis Gharan a continué à retourner le problème dans son esprit au cours des années qui ont suivi., Il soupçonnait qu’une discipline mathématique appelée la géométrie des polynômes, peu connue dans le monde de l’informatique théorique, pourrait avoir les outils dont il avait besoin. Alors, quand Karlin est venu à lui il y a deux ans suggérant qu’ils Co-conseillent un brillant nouvel étudiant diplômé nommé Nathan Klein qui avait double-spécialisé en mathématiques et violoncelle, il a dit, « OK, essayons — j’ai ce problème intéressant. »
Karlin pensait que, si rien d’autre, ce serait une occasion amusante d’en apprendre davantage sur la géométrie des polynômes., « Je ne pensais pas que nous serions en mesure de résoudre ce problème,” dit-elle.
elle et Oveis Gharan n’ont pas hésité à jeter Klein dans les profondeurs de la recherche en informatique. Oveis Gharan s’était lui-même coupé les dents sur le problème du vendeur itinérant en tant qu’étudiant diplômé en 2010. Et les deux conseillers ont convenu du bien-fondé d’attribuer des problèmes difficiles aux étudiants diplômés, en particulier au cours de leurs deux premières années, lorsqu’ils ne sont pas sous pression pour obtenir des résultats.
Les trois ont plongé dans une collaboration intense., ” C’est tout ce à quoi je pensais depuis deux ans », a déclaré Klein.
ils ont passé la première année à résoudre une version simplifiée du problème, pour avoir une idée des défis auxquels ils étaient confrontés. Mais même après avoir accompli cela, le cas général ressemblait toujours à un « coup de lune”, a déclaré Klein.
pourtant, ils avaient eu une idée de leurs outils — en particulier, la géométrie des polynômes. Un polynôme est une combinaison de termes constitués de nombres et de variables élevées à des puissances, telles que 3x2y + 8xz7., Pour étudier le problème des vendeurs itinérants, les chercheurs ont distillé une carte des villes jusqu’à un polynôme qui avait une variable pour chaque bord entre les villes, et un terme pour chaque arbre qui pourrait relier toutes les villes. Des facteurs numériques ont ensuite pondéré ces termes pour refléter la valeur de chaque bord dans la solution fractionnaire au problème du vendeur itinérant.
ce polynôme, ont-ils trouvé, a une propriété convoitée appelée « stabilité réelle”, ce qui signifie que les nombres complexes qui font évaluer le polynôme à zéro ne se trouvent jamais dans la moitié supérieure du plan complexe., La bonne chose à propos de la stabilité réelle est qu’elle reste en vigueur même lorsque vous apportez de nombreux types de modifications à votre polynôme. Ainsi, par exemple, si les chercheurs voulaient se concentrer sur des villes particulières, ils pourraient utiliser une seule variable pour représenter toutes les différentes arêtes menant à une ville, et ils pourraient définir les variables pour les arêtes dont ils ne se souciaient pas égal à 1. Comme ils manipulaient ces polynômes simplifiés, les résultats de leurs manipulations avaient encore une réelle stabilité, ouvrant la porte à un large éventail de techniques.,
cette approche a permis aux chercheurs de se familiariser avec des questions telles que la fréquence à laquelle l’algorithme serait forcé de connecter deux villes éloignées. Dans une analyse de près de 80 pages, ils ont réussi à montrer que L’algorithme Bat L’algorithme de Christofides pour le problème général des vendeurs itinérants (le document n’a pas encore été évalué par les pairs, mais les experts sont convaincus que c’est correct). Une fois le document terminé, Oveis Gharan a envoyé un e-mail à Saberi, son ancien conseiller doctoral. « Je suppose que je peux enfin obtenir mon diplôme”, a-t-il plaisanté.
