Dynamic environments are becoming central in combinatorial optimization. In such environments where the input of an optimization problem changes over time, a sequence of solutions has to be found offering both good quality, w.r.t. the objective function of the optimization problem, and stability of the returned solutions over time. To model the dynamicity of the optimization problem we adopt the multistage model of Gupta et al (ICALP 2014). Recently, it has been shown that some problems that are solvable in polynomial time in the static case become very hard even in the off-line dynamic setting. We propose to further investigate such dynamic problems and to measure the impact of the knowledge of the future on the trade-off between quality and stability. To do that we aim to take advantage of both the online learning and the competitive analysis frameworks and the interplay between the two.
Keywords : approximation, optimization discrète, online
This PhD research project has been submitted for a funding request to “Ecole Doctorale d‘Informatique, Télécommunication et d‘Electronique (EDITE)”. The PhD candidate selected by the project leader will therefore participate in the project selection process (including a file and an interview) to obtain funding.