Date : March 17, 2022, 1:30 p.m. - Room :Amphi 3 - Pôle commun

Packing and covering in geometry


Given a set of points in the plane or low dimensional euclidean plane, and a set of geometric objects, for example disks or squares, the packing problem is to select the maximum number of objects so that no point is contained in more than one object. In the covering problem, the objective is to select the smallest number of geometric objects so that all points are covered.

There are several natural variations of these problems, and in a large part, for several of these problems, a simple local search algorithm has led to near optimal solutions. In this talk, I will present an overview of the algorithm and techniques involved, and also show how local search can sometimes be combined with LP-rounding to obtain good algorithms. I will close with several open questions.