Seminar

Date : April 29, 2021, 2 p.m. - Room :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, Gödel Prize 2010, is an American researcher in theoretical computer science (currently a professor at Stony Brook University).

His research interests include problems in algorithmic geometry.
He is particularly interested in the development of approximation algorithms to solve difficult problems.
For example, his name is associated with the traveling salesman problem (TSP) for which he helped to show the existence of approximation algorithms in polynomial time.
This work earned him the 2010 Gödel Prize with Sanjeev Arora.

He is a member of the editorial board of the journals Discrete and Computational Geometry, Computational Geometry: Theory and Applications, Journal of Computational Geometry, and
Journal of Graph Algorithms and Applications, and he is one of the two editors of the International Journal of Computational Geometry and Applications.
He has also been a frequent keynote speaker at the International Algorithmic Geometry Conference SoCG.

Visio :

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

Meeting ID: 851 951 0325

Passcode: keynote

Video deposit :

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