TEILLER Alexandre

PhD student at Sorbonne University
Team : RO
https://lip6.fr/Alexandre.Teiller

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

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)

Departure date : 12/01/2020

2019-2023 Publications

All Journal articles Communications Thesis

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”, thesis, phd defence 12/01/2020, supervision Escoffier, Bruno, co-supervision : 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)