Séminaire

Date : 29 avril 2021 14:00 - Salle :Visio-conférence Keynote 1 - Approximation Algorithms for Some Geometric Packing/Covering/Routing Problems Joseph S.B Mitchell - Stony Brook University

Abstract: A fundamental class of combinatorial optimization problems involve packing and covering.

Examples include maximum independent set, dominating set, set cover, hitting set, etc. Motivated by applications in sensor networks and robotics, natural instances of such problems arise in geometric situations, such as covering points with a small number of disks, viewing "art galleries" with a small number of guards or with a mobile guard on a short route, packing disks or other shapes within a bounded domain, etc. Almost all of these problems are NP-hard even in simple two-dimensional settings.
 
The problems get even harder when we take into account uncertain data, time constraints for scheduled coverage, and routing/connectivity problems in combination with coverage constraints.

We discuss several of these geometric optimization problems from the perspective of approximation algorithms and we describe some techniques that have led to new or improved bounds or running times for selected packing, covering, and routing/coverage problems.

Biographie :

Joseph S.B. Mitchell, prix Gödel 2010, est un chercheur en informatique théorique de nationalité américaine (actuellement professeur à Stony Brook University).

Ses travaux de recherche portent sur des problèmes de géométrie algorithmique.
Il s'intéresse tout particulièrement au développement d'algorithmes d'approximation pour résoudre des problèmes difficiles.
Son nom est par exemple associé au problème du voyageur de commerce (TSP) dont il a contribué à montrer l'existence d'algorithmes d'approximations en temps polynomial.
Ces travaux lui ont valu le Prix Gödel 2010 avec Sanjeev Arora.

Il est membre du comité de rédaction des journaux Discrete and Computational Geometry, Computational Geometry: Theory and Applications, Journal of Computational Geometry, et
de Journal of Graph Algorithms and Applications, et il est l'un des deux rédacteurs en chef de la revue International Journal of Computational Geometry and Applications.
Il a aussi souvent joué les premiers rôles dans la conférence internationale de géométrie algorithmique SoCG.

Visio :

https://us02web.zoom.us/j/8519510325?pwd=Nmt5UEVaTEl0S0V0cmhTRVpPNWVkZz09

Meeting ID: 851 951 0325

Passcode: keynote

Dépôt de la vidéo :

https://opencast.dsi.uca.fr/paella/ui/watch.html?id=d5ce0a56-ae6f-4d98-a3d3-5670247cc8b4