Description
Date depot: 1 janvier 1900
Titre: Over-time optimization
Directeur de thèse:
Evripidis BAMPIS (LIP6)
Directeur de thèse:
Bruno ESCOFFIER (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Algorithmique, combinatoire
Resumé:
In classical combinatorial optimization a huge amount of work has been devoted in the computation of an optimal or near optimal solution for various optimization problems. However, in many situations the input of a problem changes over time, and a dynamic solution has to be maintained.
In these situations, when considering this over-time optimization setting, we face the challenge to design algorithms that address (1) computational complexity issues (efficient algorithms) (2) quality issues (solutions have to be good ones) (3) stability issues by having small transition costs. This latter point the fact that in over-time optimization changing one solution to another one is often costly (think to a time schedule for trains for instance) so we shall maintain some kind of stability in dynamic solutions.
We are interested in finding the best tradeoffs between these goals. Models have been recently introduced in order to consider both quality of solutions and transition costs.
The goal of this thesis is to design and analyse algorithms in the setting of over-time optimization (including computational complexity issues, approximation and parameterized algorithms,...), as well as to propose new optimization models and objectives.
Typically studied problems are graph optimization problems and scheduling problems.
Doctorant.e: Teiller Alexandre