TEILLER Alexandre

PhD graduated
Team : RO
Departure date : 12/01/2020

Supervision : Bruno ESCOFFIER

Co-supervision : BAMPIS Evripidis

Algorithmic Aspects of “Multistage” Optimization

Many systems have to be maintained while the underlying constraints, costs and/or profits change over time. Although the state of a system may evolve during time, a non-negligible transition cost is incurred for transitioning from one state to another. In order to model such situations, Gupta et al. (ICALP 2014) and Eisenstat et al. (ICALP 2014) introduced a multistage model where the input is a sequence of instances (one for each time step), and the goal is to find a sequence of solutions (one for each time step) that are both (i) near optimal for each time step and (ii) as stable as possible.
In this thesis, we first presented the multistage framework. Then we focused on the multistage Knapsack problem in its offline version and presented a PTAS. Next, we studied multistage subset maximization problems in the online setting for which we gave almost tight upper and lower bounds on the best possible competitive ratio achievable. Finally, we tackle the target-based computer-assisted orchestration problem being a direct application of the multistage framework.

Defence : 12/01/2020 - 11h - https://zoom.us/j/92160095172?pwd=WTJrL2tvTG94Qkg2WlZ6anQwcG5ZUT09

Jury members :

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)

2019-2022 Publications

  • 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)