Les informaticiens battent le record du “ vendeur itinérant ”

| |

Quand Nathan Klein a commencé ses études supérieures il y a deux ans, ses conseillers ont proposé un plan modeste: travailler ensemble sur l’un des problèmes les plus connus et les plus anciens de l’informatique théorique.

Histoire originale réimprimé avec la permission de Magazine Quanta, une publication éditoriale indépendante du Fondation Simons dont la mission est d’améliorer la compréhension publique de la science en couvrant les développements de la recherche et les tendances en mathématiques et en sciences physiques et de la vie.

Même s’ils ne parvenaient pas à le résoudre, ils se sont dit que Klein en apprendrait beaucoup. Il a accepté l’idée. «Je ne savais pas être intimidé», a-t-il dit. «J’étais juste un étudiant de première année – je ne sais pas ce qui se passe.

Maintenant, dans un article mis en ligne en juillet, Klein et ses conseillers de l’Université de Washington, Anna Karlin et Shayan Oveis Gharan, ont finalement atteint un objectif poursuivi par les informaticiens depuis près d’un demi-siècle: une meilleure façon de trouver des solutions approximatives au problème du voyageur de commerce.

Ce problème d’optimisation, qui cherche le trajet aller-retour le plus court (ou le moins cher) à travers un ensemble de villes, a des applications allant du séquençage d’ADN à la logistique de covoiturage. Au fil des décennies, il a inspiré bon nombre des avancées les plus fondamentales de l’informatique, contribuant à mettre en lumière la puissance de techniques telles que la programmation linéaire. Mais les chercheurs n’ont pas encore exploré pleinement ses possibilités – et non faute d’essayer.

Le problème du voyageur de commerce «n’est pas un problème, c’est une dépendance», comme aime à le dire Christos Papadimitriou, un expert de premier plan en complexité informatique.

La plupart des informaticiens pensent qu’il n’existe pas d’algorithme capable de trouver efficacement les meilleures solutions pour toutes les combinaisons possibles de villes. Mais en 1976, Nicos Christofides a proposé un algorithme qui trouve efficacement des solutions approximatives – des allers-retours qui sont au plus 50% plus longs que le meilleur aller-retour. À l’époque, les informaticiens s’attendaient à ce que quelqu’un améliore bientôt l’algorithme simple de Christofides et se rapproche de la vraie solution. Mais les progrès escomptés ne sont pas arrivés.

«De nombreuses personnes ont passé d’innombrables heures à essayer d’améliorer ce résultat», a déclaré Amin Saberi de l’Université de Stanford.

Maintenant, Karlin, Klein et Oveis Gharan ont prouvé qu’un algorithme conçu il y a dix ans surpasse le facteur de 50% de Christofides, bien qu’ils n’aient pu soustraire que 0,2 milliardième d’un billionième d’un billionième de pour cent. Pourtant, cette minuscule amélioration brise à la fois un blocage théorique et psychologique. Les chercheurs espèrent qu’il ouvrira les vannes à de nouvelles améliorations.

«C’est le 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 quelques problèmes fondamentaux sur lesquels les informaticiens théoriciens 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

S’il n’y a probablement pas de méthode efficace qui trouve toujours le trajet le plus court, il est possible de trouver quelque chose d’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 épine dorsale pour un circuit aller-retour, ajoutant des bords supplémentaires pour le convertir en un aller-retour.

Tout itinéraire aller-retour doit avoir un nombre pair de bords 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 au bout 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 d’arêtes. Ensuite, il a prouvé que l’aller-retour qui en résulterait ne sera jamais plus de 50% plus long que le meilleur aller-retour possible.

Ce faisant, il a conçu peut-être l’algorithme d’approximation le plus célèbre de l’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.

.

Previous

Le coronavirus vit alors que les taux d’infection au Royaume-Uni grimpent et que les pourparlers de niveau 3 se poursuivent à Sheffield et Leeds

La femme enceinte Dani Dyer s’entraîne à pousser le landau à la date du déjeuner avec Georgia Steel

Next

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.