TEILLER Alexandre

Docteur
Équipe : RO
Date de départ : 01/12/2020
https://lip6.fr/Alexandre.Teiller

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.

Soutenance : 01/12/2020

Membres du jury :

M. Bentz Cedric (CNAM) [Rapporteur]
M. Trystram Denis (Grenoble INP) [Rapporteur]
M. Bampis Evripidis (Sorbonne Université LIP6)
M. Escoffier Bruno (Sorbonne Université LIP6)
M. Agon Carlos (Sorbonne Université IRCAM)
M. Laforest Christian (ISIMA LIMOS)
Mme. Mitsou Valia (Université de Paris IRIF)

Date de départ : 01/12/2020

Publications 2019-2023

  • 2023
  • 2022
    • E. Bampis, B. Escoffier, A. Teiller : “Multistage knapsack”, Journal of Computer and System Sciences, vol. 126, pp. 106-118, (Elsevier) (2022)
  • 2021
  • 2020
  • 2019
    • E. Bampis, B. Escoffier, K. Schewior, A. Teiller : “Online Multistage Subset Maximization Problems”, 27th 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”, 44th 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)
Mentions légales
Carte du site