Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Finding Small Hitting Sets in Infinite Range Spaces of Bounded
  VC-dimension   We consider the problem of finding a small hitting set in an {\it infinite}
range space $\cF=(Q,\cR)$ of bounded VC-dimension. We show that, under
reasonably general assumptions, the infinite dimensional convex relaxation can
be solved (approximately) efficiently by multiplicative weight updates. As a
consequence, we get an algorithm that finds, for any $\delta>0$, a set of size
$O(s_{\cF}(z^*_\cF))$ that hits $(1-\delta)$-fraction of $\cR$ (with respect to
a given measure) in time proportional to $\log(\frac{1}{\delta})$, where
$s_{\cF}(\frac{1}{\epsilon})$ is the size of the smallest $\epsilon$-net the
range space admits, and $z^*_{\cF}$ is the value of the {\it fractional}
optimal solution. This {\it exponentially} improves upon previous results which
achieve the same approximation guarantees with running time proportional to
$\poly(\frac{1}{\delta})$. Our assumptions hold, for instance, in the case when
the range space represents the {\it visibility} regions of a polygon in
$\RR^2$, giving thus a deterministic polynomial time $O(\log
z^*_{\cF})$-approximation algorithm for guarding $(1-\delta)$-fraction of the
area of any given simple polygon, with running time proportional to
$\polylog(\frac{1}{\delta})$.

30
The categories of this paper are: q-alg
11
The categories of this paper are: hep-lat
28
The categories of this paper are: alg-geom
15
The categories of this paper are: nucl-ex
35
The categories of this paper are: mtrl-th
5
The categories of this paper are: gr-qc
23
The categories of this paper are: solv-int
9
The categories of this paper are: nlin
26
The categories of this paper are: bayes-an
13
The categories of this paper are: quant-ph
0
The categories of this paper are: hep-ph
2
The categories of this paper are: math
8
The categories of this paper are: hep-ex
22
The categories of this paper are: chao-dyn
7
The categories of this paper are: hep-th
31
The categories of this paper are: ao-sci