Direction de recherche : Evripidis BAMPIS, Bruno ESCOFFIER

Algorithmes en ligne et d'approximation: Au-delà des paradigmes pire cas

Cette thèse explore le paysage évolutif de l'analyse des algorithmes, des mesures traditionnelles du pire cas au cadre innovant des algorithmes d’apprentissage augmentés. Alors que l'analyse traditionnelle du pire cas a été au cœur des avancées de l'informatique théorique au cours des 50 dernières années, il existe de nombreux problèmes et algorithmes du monde réel pour lesquels l'analyse du pire cas ne fournit pas d'explication convaincante. Un exemple bien connu est le problème de la pagination en ligne, ou de la mise en cache. Dans la mise en cache, l'analyse du pire cas ne peut pas faire la distinction entre les méthodes FIFO et LRU, même si la méthode LRU est clairement supérieure en pratique.

Cela sert de motivation pour explorer des approches qui vont au-delà de l'analyse du pire cas avec un accent particulier sur le domaine émergent des algorithmes avec prédictions (algorithms learning augmented), qui a été inspiré par les progrès récents de la communauté de l'apprentissage automatique. Les algorithmes d'apprentissage automatique ont la capacité d'apprendre à partir de données passées et d'exploiter les modèles sous-jacents dans le domaine d'application, conduisant à des solutions étonnamment efficaces.

Dans le cadre d’apprentissage augmenté, on conçoit des algorithmes qui fonctionnent en conjonction avec un modèle d'apprentissage automatique en boite noire, qui leur fournit des informations prédictives sur les données. Étant donné que ces prédictions peuvent être sujettes à des erreurs, l'algorithme doit les gérer avec soin, une tâche qui introduit divers défis. Le cœur de notre travail réside dans les algorithmes en ligne, qui doivent prendre des décisions sans connaissance complète de la séquence d'entrée. Nous commençons par un problème purement en ligne qui illustre la nécessité d'une analyse au-delà du pire des cas.

Le chapitre suivant explore une nouvelle variante d'un problème en ligne classique qui donne plus de puissance à l'algorithme en ligne en fournissant des informations supplémentaires sur l'entrée. Dans les deux chapitres suivants, nous étudions deux problèmes en ligne différents à travers le prisme des algorithmes d’apprentissage augmenté. Nous concevons des algorithmes utilisant des prédictions qui surmontent les barrières computationnelles connues lorsque les prédictions sont suffisamment précises. Même lorsque les prédictions sont mauvaises, nos algorithmes maintiennent toujours des garanties du pire des cas qui sont proches des meilleures garanties réalisables sans prédictions.

Enfin, nous introduisons des schémas d'approximation d’apprentissage augmenté pour les problèmes d'optimisation NP-difficiles. Nous montrons que même un petit nombre de prédictions suffit à améliorer le temps d'exécution d'algorithmes d'approximation bien connus, dépassant les limites de calcul connues de l'analyse du pire cas.

Soutenance : 17/12/2024

Membres du jury :

Vianney Perchet, ENSAE [Rapporteur]
Ola Svensson, EPFL [Rapporteur]
Johanne Cohen, Université Paris-Saclay
Christoph Dürr, Sorbonne Université
Nicole Megow, Universität Bremen
Evripidis Bampis, Sorbonne Université
Bruno Escoffier, Sorbonne Université

Publications 2022-2024

• 2024
  • M. Xefteris : “Online and Approximation Algorithms: Beyond Worst-Case Paradigms”, soutenance de thèse, soutenance 17/12/2024, direction de recherche Bampis, Evripidis Escoffier, Bruno (2024)
• 2023
  • E. Bampis, B. Escoffier, N. Hahn, M. Xefteris : “Online TSP with Known Locations”, Algorithms and Data Structures Symposium (WADS), vol. 14079, Lecture Notes in Computer Science, Montreal, Canada, pp. 65-78, (Springer Nature Switzerland) (2023)
  • E. Bampis, B. Escoffier, Th. Gouleakis, N. Hahn, K. Lakis, G. Shahkarami, M. Xefteris : “Learning-Augmented Online TSP on Rings, Trees, Flowers and (Almost) Everywhere Else”, 31^st Annual European Symposium on Algorithms (ESA 2023), vol. 274, Leibniz International Proceedings in Informatics (LIPIcs), Amsterdam, Netherlands, pp. 12:1-12:17, (Schloss Dagstuhl - Leibniz-Zentrum für Informatik) (2023)
  • N. Hahn, M. Xefteris : “The Covering Canadian Traveller Problem Revisited”, International Symposium on Mathematical Foundations of Computer Science, vol. 272, Leibniz International Proceedings in Informatics (LIPIcs), Bordeaux, France, (Schloss Dagstuhl - Leibniz-Zentrum für Informatik) (2023)
• 2022
  • E. Bampis, B. Escoffier, M. Xefteris : “Canadian Traveller Problem with Predictions”, 20^th International Workshop on Approximation and Online Algorithms, WAOA 2022, vol. 13538, Lecture Notes in Computer Science, Potsdam, Germany, pp. 116-133 (2022)