Forschungsleitung (Direction de recherche) : Bruno ESCOFFIER

Co-Betreuung : 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.

Publikationen 2019-2023