Direction de recherche : Spyros ANGELOPOULOS
Co-encadrement : DÜRR Christoph

Algorithmes en contexte incertain: méthodes robustes et évaluation fondée sur la théorie de la décision

Dans de nombreux problèmes algorithmiques liés à la prise de décision séquentielle, l’incertitude constitue un défi central. Les éléments d’entrée peuvent arriver de manière progressive, la distribution sous-jacente peut être inconnue ou partiellement connue, et des prédictions peuvent être disponibles sans pour autant être toujours fiables. Relever ces défis nécessite de nouveaux modèles algorithmiques et des techniques adaptées aux environnements à information partielle, capables de représenter des données incertaines ou dépendant de scénarios, et permettant une analyse selon différents niveaux de précision des prédictions.

Cette thèse étudie deux cadres algorithmiques principaux intégrant l’incertitude. Le premier est celui de l’optimisation basée sur des scénarios, où l’algorithme fait face à un ensemble de scénarios représentant différentes réalisations possibles des données d’entrée. Nous présentons la première étude de structures de données fondamentales telles que les arbres de recherche binaires et les arbres de Huffman dans ce cadre, avec pour objectif de construire un arbre unique offrant de bonnes performances sur l’ensemble des scénarios. En utilisant des métriques théoriques telles que le rapport de compétitivité et le regret, nous démontrons des résultats de complexité (preuves de NP-difficulté) et proposons des algorithmes d’approximation quasi optimaux, accompagnés d’une validation expérimentale. Nous montrons également que ce cadre permet de formaliser la notion d’équité dans l’usage des structures de données.

Nous illustrons en outre l’applicabilité de cette approche au problème classique de l’inégalité du prophète, dans lequel la distribution d’entrée est supposée appartenir à un ensemble donné. Nous concevons des règles d’arrêt qui s’adaptent aux valeurs observées et garantissent des performances optimales dans le pire des cas, tout en présentant une efficacité empirique satisfaisante.

La seconde partie de la thèse est consacrée aux algorithmes en ligne augmentés par apprentissage (learning-augmented algorithms), dans lesquels l’algorithme dispose d’une prédiction pouvant être erronée. Nous étudions des approches fondées sur la théorie de la décision, permettant d’évaluer rigoureusement les performances des algorithmes en fonction de la qualité de la prédiction. En particulier, nous introduisons des métriques basées sur la distance et la gestion du risque, qui permettent une analyse plus fine et facilitent le choix de l’algorithme le plus adapté parmi une large classe de candidats.

Soutenance : 25/09/2025

Membres du jury :

Antonios Antoniadis, University of Twente, Pays-Bas [Rapporteur]
Johanne Cohen, CNRS, LISN, Université Paris-Saclay [Rapporteur]
Cristina Bazgan, Université Paris Dauphine, LAMSADE
Adi Rosen, CNRS, IRIF, Université Paris Cité
Patrice Perny, Sorbonne Université, LIP6
Michèle Sebag, CNRS, LISN, Université Paris-Saclay
Spyros Angelopoulos, CNRS, International Laboratory on Learning Systems, Montréal, Canada
Christoph Dürr, CNRS, Sorbonne Université, LIP6

Publications 2024-2025

• 2025
  • G. Melidi : “Algorithms Under Uncertainty: Robust Methods and Decision-Theoretic Evaluation”, soutenance de thèse, soutenance 25/09/2025, direction de recherche Angelopoulos, Spyros, co-encadrement : Dürr, Christoph (2025)
  • S. Angelopoulos, Ch. Dürr, G. Melidi : “Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms”, (2025)
• 2024
  • S. Angelopoulos, Ch. Dürr, A. Elenter, G. Melidi : “Scenario-Based Robust Optimization of Tree Structures”, 39^th Annual AAAI Conference on Artificial Intelligence (AAAI-25), Philadelphia (PA), United States (2024)