Claire Mathieu : l’art d’optimiser et d’approximer

C’est peut-être contre-intuitif, mais trouver la réponse exacte n’est pas toujours la meilleure solution. Certains problèmes demandent en effet un temps de calcul si long qu’il vaut mieux le réduire et se contenter d’une approximation. Cette approche est au cœur des travaux de Claire Mathieu.

Entrée au CNRS en 1990 au Département d'Informatique de l'École normale supérieure (DI ENS - CNRS/ENS - PSL/Inria) elle est passée par plusieurs laboratoires français, comme chargée de recherche puis professeure, avant de partir pour l’université Brown aux États-Unis. Claire Mathieu est revenue en France en 2012 au CNRS. Elle a occupé pendant un an une chaire au Collège de France, puis a été élue à l’Académie des sciences en 2019. La même année, elle a obtenu la médaille d’argent du CNRS.

« Je m’intéresse aux algorithmes d’optimisation de problèmes NP difficiles, c’est-à-dire qui sont au moins aussi compliqués à résoudre que des cas comme celui du voyageur de commerce, précise Claire Mathieu. J’ai notamment travaillé sur une variation de ce problème où l’on prend, en plus, en compte le volume des livraisons et les limites de stockage du véhicule, qui doit donc repasser plusieurs fois au magasin pour recharger le camion. ». Claire Mathieu a ainsi conçu un algorithme qui donne à ce problème une solution en un temps quasi polynomial, théoriquement bien plus acceptable qu’un temps exponentiel.

D’abord passionnée de mathématiques, elle a découvert l’informatique alors qu’elle était déjà étudiante à l’ENS. Claire Mathieu a bifurqué pour de bon lors de son entrée en master. Sa recherche étant de nature théorique, elle intègre toujours à ses articles des démonstrations et des théorèmes.

« En informatique fondamentale, nous démontrons comme les mathématiciens des théorèmes, mais nous sommes malgré tout plus proches des applications de la vie réelle, souligne Claire Mathieu. Si un problème est trop difficile pour être résolu en un temps raisonnable, je le rends moins général en y ajoutant des hypothèses qui, on l’espère, correspondent à des cas pratiques. »

Ces travaux l’ont notamment amenée à travailler sur le clustering hiérarchique, où l’on regroupe des données en paquets de différentes tailles, que l’on rassemble ensuite en ensembles de plus en plus grands. Sa principale contribution tient cependant à une série d’articles sur les schémas d’approximation. Ces algorithmes fournissent une solution d’optimisation en un temps raisonnable dont on choisit d’avance le degré d’approximation. « On peut ainsi annoncer dès le début que l’on n’a pas besoin d’être à moins de 20 % de l’optimum, et l’on obtient un résultat à cette précision en beaucoup moins de temps que s’il avait fallu être plus exact, » explique Claire Mathieu. Pour chaque problème, il faut concevoir un algorithme, puis démontrer un théorème qui décrit le compromis entre temps de calcul et qualité de l’approximation.

Claire Mathieu a également étudié la place des femmes dans la hiérarchie de la recherche et, à partir d’axiomes issus de la sociologie, a développé un modèle qui permet d’établir un théorème sur le plafond de verre auquel elles font face dans leur carrière. Ces travaux ont été depuis repris par d’autres équipes qui les prolongent et en testent les différentes hypothèses. Enfin, elle a été consultante pour la conception de Parcoursup, tout en encadrant un doctorant pour modéliser et analyser les algorithmes d’appariement utilisés par la plateforme. Claire Mathieu prend en effet très à cœur son rôle dans la formation.

« Nous avons vu mes différents travaux passés, mais, en tant que chercheuse sénior, je tire à présent surtout ma satisfaction des scientifiques que j’ai formés à l’étude des algorithmes, conclut Claire Mathieu. La transmission et la collaboration sont des éléments essentiels de la recherche. »