Title: On the Geometric Hitting-Set Problem.

Speaker: Esther Ezra, New York University

Time: 2:00pm-3:30pm
 
Location: Babbio Center 110
 
Abstract:
 
Given a set X of elements and a set R consisting of subsets of X (also called "ranges"), the hitting-set problem is to find a smallest subset of X with the property that each range in R contains an element of X. In a typical geometric scenario, the elements of X are points in d-space and the elements of R are simply-shaped regions in that space, e.g., X can be a set of points in the plane and R can represent a set of unit-disks. This problem is not only greatly fundamental and has been well-studied, butalso has various applications to sensor networking, art-gallery and facility location problems.
 
A related (dual) problem is the set-cover problem, where the goal is to find a smallest subcollection of R, whose union covers X. While the general (non-geometric) primal and dual problems are NP-Hard to solve, and hard to approximate up to a logarithmic factor, there exist polynomial-time approximation algorithms that yield smaller approximation factors in various geometric settings. This improvement is achieved due to the existence of small size Epsilon-nets in geometric settings. In the primal problem, an Epsilon-net is a subset of the elements in X that hit all the "heavy" regions (that is, regions that contain at least anEpsilon-fraction of the elements in X), and in the dual problem, an Epsilon-net is a subset of the regions in R that cover all the "deep" points (that is, points that are contained in at least an Epsilon-fraction of the regions). In other words, in the primal setting an Epsilon-net is a hitting set for all the heavy regions, and in the dual setting an Epsilon-net is a set-cover for all the deep points.
 
In this talk I will discuss various improved bounds on the size of Epsilon-nets for both primal and dual settings. In particular, I will emphasize the connection between combinatorial bounds on the complexity of the union of simply-shaped regions and bounds on the size of Epsilon-nets, and show how tightening the first improves the latter.
 
Joint Work with Boris Aronov (Polytechnic Institute of NYU), and Micha Sharir (Tel Aviv University).
 
Bio:
 
I am a visiting professor at Department of Computer Science at Courant Institute of Mathematical Sciences, New York University.
 
I obtained my Ph.D degree from Department of Computer Science, Tel-Aviv University in 2007. I did my Postdoctoral research  at Department of Computer Science, Duke University in the years 2007--2009, and in  Courant Institute of Mathematical Sciences in the years 2009-2011. I received NSF Fellowship in 2012.