Claire Mathieu, CNRS, Paris

Wednesday, January 24, 2024 18:00
Amphi 44, Sorbonne University - 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.

One particularly popular moment associated to the colloquium is the “Master Class” where students have the opportunity to give a short (but well-prepared) presentation of his/her work. Each presentation (10 minutes) is followed by an open discussion with the guest speaker (15 minutes) who gives a detailed feedback. The complete program is provided here.