Pour les problèmes les plus difficiles de l'optimisation combinatoire, la solution algorithmique est souvent précédée de théorèmes qui révèlent la structure du problème, ou qui donnent une « bonne caractérisation », notion clé qui permet de justifier la réponse. Nous développons aussi bien ces théorèmes que leurs conséquences algorithmiques, ou des résultats négatifs qui permettent à nos collègues et quelquefois à nous-mêmes, de construire des algorithmes d'approximation. Sur un plan purement théorique, nous nous intéressons à des objets mathématiques dont les solutions contribuent à une bibliothèque de connaissances prête à être utilisée le moment venu. Ainsi, nous travaillons sur la théorie des couplages (T-joins, maxfix covers), les chemins disjoints dans les graphes (routage, multiflots), ou des problèmes de couvertures optimales.
