Aller au menu Aller au contenu
Combinatorial Optimisation
Laboratory of Grenoble for sciences of conception, optimisation and production
Combinatorial Optimisation

Problem analysis : good characterization, complexity and algorithms

MoatsFor the hardest problems in Combinatorial Optimization, algorithms are usually preceded by theorems revealing the structure of the problem, or giving a "good" characterization, which justifies the answer. We develop these theorems as well as their algorithmic consequences, or the negative results orienting the research to approximation algorithms.
From the theoretical point of view, we are interested in mathematical objects from Matching theory, like T-joins, and from Network flow theory. The objects we study are widely used and any theoretical progress on them has immediate applied consequences. We are also interested in applied problems, like the Travelling Salesman Problem, or its variants, like vehicle routing.

Written by Louis Esperet

Date of update January 27, 2015

Communauté Université Grenoble Alpes
To improve the quality of this site and the service rendered to the user, we use cookies audience measurement. By continuing your visit to this site, you agree to our use of cookies for this purpose. More