Consider the following setting:

Let $(X,d)$ be a metric space and let $S$ be a finite subset of $X$. An $\epsilon$-cover of $S$ is any subset $C\subset S$ such that $$ \max_{x\in S} d(x,C)\leq \epsilon, $$ where $d(x,C)=\min_{y\in C} d(x,y)$. Let's call the $\epsilon$-covering number of $S$, denoted by $N(S,\epsilon)$, the size of its minimal $\epsilon$-cover: $$ N(S,\epsilon)=\min\{ |C| \mid C \text{is an $\epsilon$-covering of } S\}. $$

My question is the following: Are there any good approximation algorithms for computing the covering number? I am aware of an algorithm based on farthest-first traversal that outputs a number $N$ such that $N(S,\epsilon)\leq N \leq N(S,\epsilon/2)$. Is there anything out there which does better?

  • 2
    $\begingroup$ (1) By reduction to set cover presumably you can get $N$ such that $N(S,\epsilon) \le N \le \log(n)*N(S,\epsilon)$, where $n$ is the number of points in the metric space. In some settings (e.g. if the set system has bounded VC dimension) you can reduce the $\log n$ to a constant. (2) You can in some sense reduce dominating set to your problem: given an instance of dominating set, give weight 1 to all edges and add all missing edges giving them weight 2. Then (taking $\epsilon=1$), a dominating set of size $N$ corresponds to an $\epsilon$-cover of size $N$... $\endgroup$ – Neal Young Jul 15 '14 at 20:13
  • 2
    $\begingroup$ ...and the set-cover reduction shows that in the worst case you can not do any better than log n approximation, unless pigs can fly, and P=NP. This is because set cover can not be approximated better than log(n) factor in general... $\endgroup$ – Sariel Har-Peled Jul 15 '14 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.