Un nouvel algorithme peut considérablement rationaliser les solutions au problème du « débit maximal »

Trouver le moyen le plus efficace de transporter des objets sur un réseau comme le réseau routier américain ou Internet est un problème qui pèse sur les mathématiciens et les informaticiens depuis des décennies.

Pour résoudre le problème, les chercheurs ont traditionnellement utilisé un algorithme de débit maximal, également connu sous le nom de débit maximal, dans lequel un réseau est représenté sous la forme d'un graphique avec une série de nœuds, appelés sommets, et des lignes de connexion entre eux, appelées arêtes.

Étant donné que chaque bord a une capacité maximale - tout comme les routes ou les câbles à fibres optiques utilisés pour transmettre des informations sur Internet - ces algorithmes tentent de trouver le moyen le plus efficace d'envoyer des marchandises d'un nœud du graphe à un autre, sans dépasser ces contraintes.

Mais comme la taille des réseaux comme Internet a augmenté de façon exponentielle, il est souvent prohibitif de résoudre ces problèmes à l'aide de techniques informatiques traditionnelles, selon Jonathan Kelner, professeur agrégé de mathématiques appliquées au MIT et membre du MIT. Laboratoire d'informatique et d'intelligence artificielle (CSAIL).

Ainsi, dans un article qui sera présenté au Symposium ACM-SIAM sur les algorithmes discrets à Portland, Oregon, cette semaine, Kelner et son collègue Lorenzo Orecchia, professeur de mathématiques appliquées, aux côtés des étudiants diplômés Yin Tat Lee et Aaron Sidford, décriront un nouvel algorithme théorique qui peut réduire considérablement le nombre d'opérations nécessaires pour résoudre le problème du débit maximal, permettant de s'attaquer même à des réseaux énormes comme Internet ou le génome humain.

IMAGE : CHRISTINE DANILOFF / AVEC

Il y a eu récemment une explosion de la taille des graphiques étudiés, dit Kelner. Par exemple, si vous vouliez acheminer le trafic sur Internet, étudier toutes les connexions sur Facebook ou analyser des données génomiques, vous pourriez facilement vous retrouver avec des graphiques avec des millions, des milliards ou même des trillions d'arêtes.

Les précédents algorithmes de débit maximal sont arrivés au problème un bord, ou un chemin, à la fois, dit Kelner. Ainsi, par exemple, lors de l'envoi d'articles du nœud A au nœud B, les algorithmes transmettent une partie des marchandises sur un chemin, jusqu'à ce qu'ils atteignent leur capacité maximale, puis commencent à en envoyer sur le chemin suivant.

De nombreux algorithmes précédents, selon Kelner, trouveraient un chemin du point A au point B, enverraient du flux le long de celui-ci, puis diraient : « étant donné ce que j'ai déjà fait, puis-je trouver un autre chemin le long duquel je peux envoyer plus ? » Lorsque l'on a besoin d'envoyer du flux simultanément sur de nombreux chemins différents, cela conduit à une limitation intrinsèque de la vitesse de l'algorithme.

Mais en 2011, Kelner, l'étudiant diplômé du CSAIL Aleksander Madry, le premier cycle en mathématiques Paul Christiano et des collègues de l'Université de Yale et de l'Université de Californie du Sud ont développé une technique pour analyser tous les chemins simultanément.

Les chercheurs ont considéré le graphique comme un ensemble de résistances électriques, puis ont imaginé connecter une batterie au nœud A et une terre au nœud B, et permettre au courant de circuler dans le réseau. Le courant électrique ne choisit pas un seul chemin, il enverra un peu de courant sur chaque résistance du réseau, dit Kelner. Il sonde donc l'ensemble du graphe globalement, en étudiant de nombreux chemins en même temps.

Cela a permis au nouvel algorithme de résoudre le problème du débit maximal beaucoup plus rapidement que les tentatives précédentes.

Maintenant, l'équipe du MIT a développé une technique pour réduire encore plus le temps d'exécution, permettant d'analyser même des réseaux gigantesques, explique Kelner.

Contrairement aux algorithmes précédents, qui considéraient tous les chemins d'un graphique comme égaux, la nouvelle technique identifie les routes qui créent un goulot d'étranglement au sein du réseau. L'algorithme de l'équipe divise chaque graphique en clusters de nœuds bien connectés et les chemins entre eux qui créent des goulots d'étranglement, explique Kelner.

Notre algorithme détermine quelles parties du graphique peuvent facilement acheminer ce dont ils ont besoin et quelles parties sont les goulots d'étranglement. Cela vous permet de vous concentrer sur les zones à problèmes et la structure de haut niveau, au lieu de passer beaucoup de temps à prendre des décisions sans importance, ce qui signifie que vous pouvez utiliser votre temps beaucoup plus efficacement, dit-il.

Le résultat est un algorithme presque linéaire, dit Kelner, ce qui signifie que le temps nécessaire pour résoudre un problème est très proche d'être directement proportionnel au nombre de nœuds sur le réseau. Donc, si le nombre de nœuds sur le graphique est multiplié par 10, le temps serait multiplié par quelque chose de très proche de 10, au lieu d'être multiplié par 100 ou 1 000, dit-il. Cela signifie qu'il évolue essentiellement aussi bien que vous pouvez l'espérer avec la taille de l'entrée, dit-il.

Shanghua Teng, professeur d'informatique à l'Université de Californie du Sud qui n'était pas impliqué dans le dernier article, affirme qu'il représente une percée majeure dans les algorithmes de graphes et les logiciels d'optimisation.

Cet article, qui a remporté le prix du meilleur article à la conférence [ACM-SIAM], est le résultat des efforts soutenus de Kelner et de ses collègues dans l'application des flux électriques pour concevoir des algorithmes de graphes efficaces, explique Teng. Le document contient un éventail étonnant de contributions techniques.

cacher