Hitting sets when the VC-dimension is small

approximate with a ratio of $c\log m$, for some constant c, where m is the
number of sets in the set system.

Broennimann & Goodrich showed that an $O(\log(OPT))$ approximation ratio
is achievable in polynomial time if the VC-dimension of the set system is
constant. Moreover, their algorithm achieves a constant approximation
ratio if the set system admits $\epsilon$-nets of size $O(1/\epsilon)$.

I will start this talk by defining the relevant terms (e.g.,
VC-dimension and $\epsilon$-nets), presenting the main theorems, and
discussing a few examples from Matousek's book on Discrete Geometry. I
will then present a simple approximation algorithm that builds on
Pach & Agarwal. This algorithm only requires (approximately) solving a
hitting set linear program and finding one $\epsilon$-net.

A few extensions will be mentioned, such as: parallelization and
dealing with the min-cost hitting set problem.

Joint work with Dror Rawitz and Moni Shahar.