Séminaire


Date : 21 juin 2019 13:30 - Salle :Salle du conseil

Packing and Covering with non-piercing regions


Rajiv Raman - Indraprastha Institute of Information Technology DELHY, India

A region is a set in the plane bounded by a Jordan curve.
A set of regions is non-piercing if for any pair of regions A, B in the set, both A\B and B\A are connected sets.

 

We present results on several packing and covering problemswith non-piercing regions. A classic special case of this class
of problems is the Set Cover problem with disks: Given a set ofdisks in the plane and a set of points find the smallest number
of disks required to cover all the points.

 

We show that a simple local search algorithm yields a PTAS formany of these problems. The key to the analysis is the question
of the existence of a graph with some special properties. We showthe existence of such a graph that yields a unified proof for several
packing and covering problems.

 

We also sketch how, with some additional ideas, we can show that a localsearch algorithm is a PTAS for some extensions of the classic packing and covering problems.