Des chercheurs réfutent une croyance largement répandue concernant les algorithmes en ligne | Magazine Quanta

Dans la vie, nous devons parfois prendre des décisions sans disposer de toutes les informations souhaitées ; c'est également vrai en informatique. C’est le domaine des algorithmes en ligne qui, malgré leur nom, n’impliquent pas nécessairement Internet. Il s’agit plutôt de stratégies de résolution de problèmes qui réagissent aux données au fur et à mesure qu’elles arrivent, sans aucune connaissance de ce qui pourrait suivre. Cette capacité à faire face à l'incertitude rend ces algorithmes utiles pour résoudre des problèmes concrets, comme la gestion de la mémoire sur un ordinateur portable ou le choix des publicités à afficher auprès des personnes qui naviguent sur le Web.

Les chercheurs étudient des versions généralisées de ces problèmes pour rechercher de nouvelles méthodes permettant de les résoudre. Parmi les plus célèbres, on trouve le « k-problème de serveur », qui décrit la tâche épineuse consistant à envoyer une flotte d'agents pour répondre aux demandes arrivant une par une. Il peut s'agir de réparateurs, de pompiers ou encore de vendeurs de glaces itinérants.

"C'est très simple de définir ce problème", a déclaré Marcin Bieńkowski, chercheur en algorithmique à l'Université de Wrocław en Pologne. Mais cela « s’avère étrangement difficile ». Depuis que les chercheurs ont commencé à s'attaquer au k-problème de serveur à la fin des années 1980, ils se sont demandés exactement dans quelle mesure les algorithmes en ligne pouvaient gérer cette tâche.

Au fil des décennies, les chercheurs ont commencé à croire qu'il existe un certain niveau de performance algorithmique que l'on peut toujours atteindre pour le k-problème de serveur. Ainsi, quelle que soit la version du problème auquel vous êtes confronté, il existera un algorithme qui atteindra cet objectif. Mais dans un article publié pour la première fois en ligne en novembre dernier, trois informaticiens montré que ce n'est pas toujours réalisable. Dans certains cas, tous les algorithmes échouent.

"Je suis heureux de dire que ce fut une grande surprise pour moi", a déclaré Anupam Gupta, qui étudie les algorithmes à l'Université Carnegie Mellon et n'a pas été impliqué dans l'article. L’ouvrage offre « un aperçu plus approfondi du problème central dans ce domaine ».

Les informaticiens d’abord a décrit ce problème en 1988. Pour avoir une idée, imaginons une entreprise qui emploie des plombiers. Au fur et à mesure que les appels arrivent, l’entreprise doit décider quel plombier se rendra à quel endroit. L'objectif de l'entreprise — et l'objectif d'un algorithme pour le k-Le problème du serveur est de minimiser la distance totale parcourue par tous les plombiers.

Le problème est que l’entreprise ne sait pas à l’avance d’où proviendront les appels. Si c’était le cas, alors il pourrait s’appuyer sur un « algorithme hors ligne » qui connaît l’avenir. En particulier, il pourrait utiliser une stratégie de répartition idéale qui trouve une solution avec le moins de déplacements totaux pour n'importe quelle chaîne d'appels. Aucun algorithme en ligne ne pourra jamais le battre, ni même l’égaler de manière fiable.

Mais les chercheurs veulent s’en rapprocher le plus possible. Ils mesurent les performances d'un algorithme en ligne en comparant la distance parcourue dans chaque stratégie et en calculant ce que l'on appelle le ratio de compétitivité. Les concepteurs d’algorithmes tentent d’élaborer des stratégies en ligne qui se rapprochent de l’idéal hors ligne, en réduisant ce ratio à 1.

Imaginons que notre entreprise de plomberie ne compte que deux plombiers et qu'elle ne dessert qu'une seule et longue rue. Les appels arrivent un à un. Une première approche raisonnable, connue sous le nom d’algorithme glouton, consisterait à envoyer le plombier le plus proche de l’emplacement de chaque appel entrant. Mais voici un scénario dans lequel cet algorithme rencontre des difficultés : imaginez qu'un plombier commence à l'extrémité ouest de la rue et l'autre à l'extrémité est, et que tous les appels proviennent de deux maisons voisines à l'extrémité ouest. Dans ce cas, un plombier ne bouge jamais tandis que l’autre accumule les kilomètres dans ces deux maisons. Rétrospectivement, la meilleure stratégie aurait été de déplacer les deux plombiers dans la zone sujette aux problèmes – mais, hélas, on ne pouvait pas savoir où cela allait se passer.

Même ainsi, a déclaré Bieńkowski, il est possible de faire mieux que l'algorithme glouton. Le "double couverture" L'algorithme déplace les deux plombiers au même rythme vers tout appel qui tombe entre eux, jusqu'à ce que l'un d'eux l'atteigne. Cette méthode permet d’obtenir un ratio de compétitivité inférieur à celui de l’algorithme glouton.

Bien que ce problème abstrait ne soit pas pertinent pour les véritables entreprises de plomberie, « le k"Le problème du serveur en lui-même est vraiment la question déterminante" dans l'informatique en ligne, a déclaré Yuval Rabani, un informaticien de l’Université hébraïque de Jérusalem qui a co-écrit l’article récent. Cela s'explique en partie par le fait que les outils et techniques développés au cours des travaux sur le kLes problèmes de serveur trouvent souvent des applications ailleurs dans l’étude des algorithmes en ligne, et même en dehors de celle-ci.

«Cela fait partie de la magie du travail sur les algorithmes», a-t-il déclaré.

Lorsqu’ils étudient ces problèmes, les scientifiques aiment les considérer comme des jeux contre un adversaire. L’adversaire choisit une séquence diabolique de requêtes pour rendre l’algorithme en ligne aussi mauvais que possible par rapport à son homologue hors ligne. Pour priver l'adversaire d'une partie de sa puissance, les chercheurs utilisent des algorithmes qui incluent décisions aléatoires.

Cette stratégie est assez efficace, et les chercheurs soupçonnent depuis le début des années 1990 qu'il est toujours possible de trouver un algorithme aléatoire qui atteint un objectif de performance spécifique : un ratio de compétition proportionnel au log. k, Où k est le nombre d'agents. C'est ce qu'on appelle le randomisé k- conjecture du serveur, et les chercheurs ont montré que c'est vrai pour certains espaces, ou ensembles de points spécifiques (l'équivalent de maisons qui pourraient faire appel à des plombiers). Mais cela n’a pas été prouvé dans tous les cas.

Comme la plupart des chercheurs, Rabani et ses co-auteurs — Sébastien Bubeck de Microsoft Research et Christian Coester de l'Université d'Oxford - a pensé que la conjecture était vraie. "Je n'avais aucune raison d'en douter", a déclaré Coester.

Mais cela a commencé à changer alors qu’ils travaillaient sur un autre problème en ligne. Il avait des liens avec le k-problème de serveur, et la limite inférieure connue du ratio de compétitivité était étonnamment élevée. Cela leur a fait penser qu'il s'agissait peut-être d'un objectif aussi bas que le journal k pour le k-Le problème du serveur était trop optimiste.

Rabani a déclaré que c'était Coester qui avait le premier suggéré que le groupe randomisé k-la conjecture du serveur pourrait être fausse. "Dès qu'il l'a dit, tout a pris un sens."

Pour réfuter cette hypothèse, les auteurs ont joué l'adversaire, créant une tempête parfaite qui empêcherait tout algorithme en ligne d'atteindre un ratio compétitif de log k. Leur stratégie comportait deux parties : ils construisaient une famille d'espaces complexes de type fractal et concevaient une distribution de séquences de requêtes qui serait difficile pour n'importe quel algorithme possible. Dès le premier mouvement de l'algorithme, la structure de l'espace l'obligeait à choisir entre deux chemins identiques, dont l'un nécessiterait éventuellement un déplacement supplémentaire en fonction des demandes. Ensuite, les auteurs ont utilisé une méthode appelée récursion pour créer des espaces qui multipliaient ces points de décision, forçant l'algorithme dans un bourbier de mauvaises options et augmentant les coûts.

Les choix ont rappelé à Rabani le poème de Robert Frost «La route non empruntée,» dans lequel un voyageur contemple deux chemins potentiels à travers un bois jaune. « Nous appliquons simplement le poème de manière récursive », a-t-il plaisanté. "Et puis les choses vont vraiment mal."

Les auteurs ont montré que, dans les espaces qu’ils avaient construits, un algorithme randomisé ne pourra jamais atteindre un ratio de compétitivité meilleur que (log k)², poussant un objectif universel de journalisation k à jamais hors de portée. Ils avaient réfuté la conjecture.

Cette œuvre, qui a remporté un Prix ​​du meilleur papier au Symposium 2023 sur la théorie de l'informatique, marque une étape « solidement théorique », a déclaré Gupta. Ce type de résultat permet d’indiquer quel type de performances nous pouvons espérer de nos algorithmes. Dans la pratique, cependant, les concepteurs d’algorithmes ne prévoient souvent pas les pires scénarios, avec un adversaire tout-puissant et une ignorance totale de l’avenir. Lorsque les algorithmes sont utilisés pour résoudre des problèmes du monde réel, ils dépassent souvent les attentes théoriques.

L'article, qui prouve également les seuils pour les algorithmes randomisés utilisés pour d'autres problèmes, pourrait également avoir des implications pour les travaux futurs dans ce domaine. Le résultat « met clairement en évidence la puissance » de la technique utilisée par les auteurs, a déclaré Gupta.

Peut-être que ces découvertes futures défieront les attentes des chercheurs comme celle-ci, a déclaré Rabani. "C'est l'un des cas où il fait vraiment du bien de se tromper."

Quanta mène une série d’enquêtes pour mieux servir notre public. Prenez notre enquête auprès des lecteurs en informatique et vous serez inscrit pour gagner gratuitement Quanta marchandise.