Ce projet de recherche doctorale est publié a été réalisé par Evripidis BAMPIS

Description d'un projet de recherche doctoral

Beyond online learning and competitive analysis for combinatorial optimization over time

Mots clés :

Résumé du projet de recherche (Langue 1)

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 use the following model: we are given a time horizon of T time steps, and at each time step an instance I_1, I_2,..., I_T. It is tempting to try to solve the problem for every instance independently. However, there is a non-negligible transition cost for adopting modifications to a given solution. Different settings are induced depending on the degree of knowledge of the future: the offline setting where the whole sequence of instances is known in advance, the 1-lookahead (online) setting where at time t only the instance I_t is known, and the k-lookahead (semi-online) setting where at time t the instances at times t, t+1,..., t+k, with k>=1, are known. 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. This is the case for the minimum weighted perfect matching problem. On the positive side, in the off-line setting good approximation algorithms have been proposed for fair resource allocation or matroid maintenance problems. Also some algorithms with good competitive ratio have been proposed for specific problems in the semi-online setting. We propose to further investigate such dynamic problems in the semi-online setting 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 for the online setting and the interplay between the two. While there are some important differences between these two approaches, some recent works succeeded to bring them closer together. Our goal will be to follow this research direction and to investigate whether it is possible to extend this success by closing the gap between learning from experts and the more general k-lookahead setting.