Claire Mathieu, CNRS, Paris

Mercredi 24 janvier 2024 18 h
Amphi 44, Sorbonne Université - Faculté des Sciences

Vehicle routing and approximation algorithms

Claire Mathieu's research area concerns the design and analysis of algorithms, particularly the design of approximation algorithms for combinatorial optimization. She is a research director in Computer Science at CNRS. She was a recipient of the Computer Science Chair at College de France, participated in the design of the French Parcoursup platform for college admissions, received the 2019 CNRS Silver Medal, belongs to the French Academy of Science, and is an EATCS Fellow since 2023.

The traveling salesman problem, one of the most celebrated problems of Computer Science, is a simplified abstraction of many routing problems. In vehicle routing, the questions are brought one step closer to applications by taking into account some additional constraints taking into account the fact that real-life deliveries are done with a vehicle. Typically, its capacity is limited and the driver must go back to the depot to refill the vehicle with additional items to be delivered. I will present a range of questions and results for vehicle routing problems, with a focus on theoretical approximations. Most of the results presented are joint with Hang Zhou.

L'un des moment particulièrement apprécié lors du colloquium est la « Masterclass » au cours de laquelle quelques doctorants du laboratoires ont l'opportunité de présenter leurs travaux à l'invité(e). Chaque présentation est suivie d'une discussion approfondie. Le programme complet est donné dans le document suivant.