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

> GSCOP_Research > GSCOP_OC

Problem analysis : good characterization, complexity and algorithms

For 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.

Date of update January 27, 2015

Université Grenoble Alpes