La conjecture des k-serveurs enfin prouvée
Original : The k-server conjecture is true
Pourquoi c'est important
Une conjecture centrale de l'informatique théorique résolue après plus de 35 ans de recherche.
Les chercheurs Christian Coester, Elias Koutsoupias et Marek Zbysiński ont publié le 14 septembre 2026 sur arXiv une preuve de la conjecture des k-serveurs, un problème ouvert depuis plus de 35 ans en algorithmique en ligne, démontrant que le work function algorithm atteint un ratio de compétitivité k.
La conjecture des k-serveurs, formulée par Manasse, McGeogh et Sleator en 1988, affirme qu'un algorithme déterministe en ligne peut atteindre un ratio de compétitivité k sur tout espace métrique, avec k serveurs. Ce problème est l'un des plus célèbres de l'algorithmique en ligne. Coester, Koutsoupias et Zbysiński prouvent que le work function algorithm — un candidat historique — satisfait effectivement cette borne. La preuve repose sur une représentation algébrique de la fonction de travail sous forme de matrice, où les opérations de minimum et d'addition correspondent à l'addition et à la multiplication d'expressions formelles. Chaque valeur de la fonction de travail correspond au déterminant de k colonnes de cette matrice. L'arrivée d'une requête met à jour la représentation via un changement de base et un remplacement de ligne. L'analyse amortie utilise une fonction potentiel définie à partir d'une matrice élargie. Le papier de 22 Ko est disponible en PDF et HTML sur arXiv (arXiv:2609.15979).