Relatore : Spyros ANGELOPOULOS
Co-relazione : DÜRR Christoph

Algorithms Under Uncertainty: Robust Methods and Decision-Theoretic Evaluation

In many algorithmic problems involving sequential decision-making, uncertainty is a central challenge. Input items may arrive over time, the input distribution may be unknown or partially known, and predictions may be available but not always accurate. Addressing these challenges requires new algorithmic models and techniques which are suited for partial-information settings, can capture uncertain or scenario-based inputs, and can support analysis across varying levels of prediction accuracy.

This thesis studies two main algorithmic settings that involve uncertainty. The first setting is scenario-based optimization, in which the algorithm is faced with a set of input scenarios, each representing a distinct possibility that a certain input materializes. We present the first study of fundamental data structures such as Binary Search Trees and Huffman Trees under scenario-based optimization, where the goal is to obtain a single tree that performs well across all scenarios. Using theoretical performance metrics such as the competitive ratio and the regret, we give NP-hardness proofs and near-tight approximations, as well as a validating experimental analysis. We also show that this framework can help us capture the notion of fairness, in the context of data structures.

Furthermore, we apply the scenario-based approach to the classic prophet inequality problem, where the input distribution is known to belong to a given set of distributions. We design stopping rules that adapt to observed values and achieve optimal worst-case guarantees, while simultaneously demonstrating efficient empirical performance. The second part of this thesis focuses on learning-augmented algorithms, in which the online algorithm is enhanced with a potentially erroneous prediction. Here, we study approaches based on decision theory that allow us to rigorously quantify and compare the performance of algorithms as the prediction quality varies. Specifically, we introduce distance-based and risk-aware metrics that allow for a refined performance analysis and help select the most suitable algorithm from a broad class of candidates.

Difesa : 09/25/2025

Membri della commissione :

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

Pubblicazioni 2024-2025

• 2025
  • G. Melidi : “Algorithms Under Uncertainty: Robust Methods and Decision-Theoretic Evaluation”, these, difesa 09/25/2025, relatore Angelopoulos, Spyros, co-relazione : 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)