Date : June 27, 2019, 11 a.m. - Room :Salle du conseil

Local Search for Geometric Optimization Problems

Nabil MUSTAFA, Professeur - ESIEE Paris

Local-search is an intuitive approach towards solving combinatorial optimization problems: start with any feasible solution, and try to improve it by local improvements. Like other greedy approaches, it can fail to find the global optimum by getting stuck on a locally optimal solution. In this talk I will present the ideas and techniques behind the use of local-search in the design of provably good approximation algorithms for some combinatorial problems. Joint work with my PhD student Bruno Jartoux, and Daniel Antunes and Claire Mathieu.