Научны(е)й руководител(и)ь : Bruno ESCOFFIER

Со-руководитель : 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.

Публикации 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”, диссертация, Защита диссертаций 01.12.2020, Научны(е)й руководител(и)ь Escoffier, Bruno, Со-руководитель : 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)