Titre :  QPTAS for Geometric Set-Cover Problems via Optimal Separators

Exposant : Mustafa Nabil

Résumé :  
Geometric set-cover problems arise naturally in several basic settings, and  therefore the problem of computing small set covers has been studied extensively. However, after more than three decades of research, PTAS for even basic scenarios are still lacking. A prominent example is of weighted disks in the plane for which, after a series of papers, Varadarajan [2009] and Chan et. al. [2012] showed a O(1)-approximation algorithm for computing minimum-weight set-covers. For the fundamental class of objects called pseudodisks (which includes disks, unit-height rectangles, translates of a convex set), even a PTAS for the unweighted case is a long-standing open problem. We will present a QPTAS for both these problems based on the separator framework of Adamaszek and Weise [2013, 2014]. Joint work with Rajiv Raman and Saurabh Ray.