<p>Consider the following setting:</p>

<p>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\}.
$$</p>

<p>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?</p>

CC BY-SA 3.0
2014-07-15T20:13:09.673Z
(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$...
Neal Young
CC BY-SA 3.0
2014-07-15T23:27:40.367Z
...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...
Sariel Har-Peled
<approximation-algorithms><metric-spaces><covering-problems>
Approximation of covering number in metric space
sirolf
# Approximation of covering number in metric space

(Asked by: username_0 on 2014-07-14)

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?

**Tags:** approximation-algorithms, metric-spaces, covering-problems
> **Comments:**
> **username_1**: (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$...  
> **username_2**: ...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...  

---

## 0 answers

