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.