Meike Neuwohner et l'optimisation combinatoire

Quel est votre domaine de recherche ?

Meike Neuwohner : Mon domaine de recherche est l’optimisation combinatoire. Je travaille surtout sur les algorithmes d’approximation pour les problèmes NP-difficiles. Ces problèmes ne permettent pas d'obtenir des algorithmes exacts et efficaces. J'essaie donc de développer des algorithmes efficaces qui permettent de trouver des solutions dont la qualité est démontrable. Par exemple, des solutions dont le coût est au plus deux fois supérieur à celui d'une solution optimale. C'est ce qu'on appelle un algorithme d'approximation.

Dans ma thèse de doctorat, j’ai examiné le problème weighted k-Set Packing et j’ai analysé les algorithmes d’approximation basés sur la recherche locale. Pendant mon post-doc, j’ai commencé à travailler aussi sur des questions plus structurelles, y compris concernant les graphes orientés ou la structure des matrices totalement unimodulaires. Récemment, j’ai travaillé sur des algorithmes d’approximation pour des problèmes liés au Network Design.

Qu’avez-vous fait avant d’entrer au CNRS ? Pourquoi avoir choisi le CNRS ?

M.N. De 2015 à 2020, j’ai étudié les mathématiques à l’université de Bonn en Allemagne, j’y ai fait aussi mon doctorat à l’institut des mathématiques discrètes. Après avoir soutenu ma thèse en décembre 2023, je suis partie à Londres où j’ai fait un post-doc dans le département des mathématiques à la London School of Economics and Political Science. En 2025, j’ai passé le concours du CNRS et j’ai commencé comme chargée de recherche CNRS à l'ENS en novembre 2025. J’ai choisi le CNRS parce que j’aime beaucoup ce qu’il m’offre dont la liberté de me concentrer entièrement sur ma recherche sans les charges d’enseignement et d’administration qui viennent normalement avec une position permanente. Le fait que j’ai appris la langue française à l’école a aussi joué un rôle et m'a beaucoup aidé dans ma carrière.

Qu’est-ce que qui vous a amené à faire des sciences informatiques ?

M.N. Quand j’étais à l’école j’ai participé à plusieurs compétitions de mathématiques, ce qui a fait grandir ma passion pour résoudre des problèmes et pour analyser et comprendre leurs structures. Ce moment où tout bascule et s’aligne est profondément stimulant. Pendant mes études, j’ai travaillé comme assistante à l’institut des mathématiques discrètes dans un projet appliqué concernant le « VLSI chip design ». Ma thèse de bachelor a abordé un problème émergent de ce projet. En l’étudiant, j’ai progressivement saisi sa structure, ce qui a éveillé mon intérêt pour l’optimisation combinatoire, une discipline à l’intersection des mathématiques et de l’informatique.