Direction de recherche : Bruno ESCOFFIER

Co-encadrement : BAMPIS Evripidis

Aspects Algorithmiques de l’Optimisation «Multistage»

Beaucoup de systèmes ont le besoin d’être maintenus alors que leurs contraintes, coûts et/ou profits sous-jacents changent au cours du temps. Bien que l’état d’un système peut être amené à évoluer au cours du temps, un coût de transition non négligeable peut être engendré par le fait de passer d’un état à un autre. Afin de modéliser de telles situations, Gupta et al. (ICALP 2014) et Eisenstat et al. (ICALP 2014) ont introduit un modèle multistage où en entrée est donnée une séquence d’instances (une pour chaque pas de temps), et l’objectif est de trouver une séquence de solutions (une pour chaque pas de temps) qui sont à la fois (i) proche de l’optimalité pour chaque pas de temps et (ii) aussi stable que possible.
Dans cette thèse, nous avons tout d’abord présenté le cadre multistage. Ensuite, nous nous sommes concentrés sur le problème du Sac-à-Dos multistage dans sa version offline et avons présenté un PTAS. Ensuite, nous avons étudié les problèmes multistage de maximisation de sous-ensemble dans un cadre online pour lesquels nous avons donné des bornes inférieures et supérieures presque serrées sur les meilleures rapports de compétitivité possibles. Enfin, nous nous sommes intéressés au problème d’orchestration assistée par ordinateur avec son cible, étant une application directe du cadre multistage.

Publications 2019-2023

• 2023
  • E. Bampis, C.‑E. Cella, B. Escoffier, M. Rocco, A. Teiller : “Target-based computer-assisted orchestration: Complexity and approximation algorithms”, European Journal of Operational Research, vol. 304 (3), pp. 926-938, (Elsevier) (2023)
• 2022
  • E. Bampis, B. Escoffier, A. Teiller : “Multistage knapsack”, Journal of Computer and System Sciences, vol. 126, pp. 106-118, (Elsevier) (2022)
• 2021
  • E. Bampis, B. Escoffier, K. Schewior, A. Teiller : “Online Multistage Subset Maximization Problems”, Algorithmica, vol. 83 (8), pp. 2374-2399, (Springer Verlag) (2021)
• 2020
  • A. Teiller : “Algorithmic Aspects of “Multistage” Optimization”, soutenance de thèse, soutenance 01/12/2020, direction de recherche Escoffier, Bruno, co-encadrement : Bampis, Evripidis (2020)
• 2019
  • E. Bampis, B. Escoffier, K. Schewior, A. Teiller : “Online Multistage Subset Maximization Problems”, 27^th Annual European Symposium on Algorithms (ESA 2019), vol. 144, Leibniz International Proceedings in Informatics (LIPIcs), Munich, Germany, (Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik) (2019)
  • E. Bampis, B. Escoffier, A. Teiller : “Multistage Knapsack”, 44^th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), vol. 138, Aachen, Germany, pp. 22:1-22:14, (Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik) (2019)