<p>This problem generalizes dominating set: given an unweighted graph, there exists a set of k centers such that all other vertices are at distance 1 from them if and only if there exists a dominating set of size k.</p>

<p>Dominating set is hard to approximate with a ratio better than $\ln n$. In the above observation the optimal value for the k-center problem is either 1 or at least 2. Let $A$ be a $(c,2-\epsilon)$ bi-criteria approximation for $k$-center for some $c &lt; \ln n$. If a dominating set of size $k$ exists, then the corresponding $k$-center problem would have optimum cost of 1, and $A$ would return a solution of cost at most $2-\epsilon$ using at most $k \ln n$ centers. Thus, $A$ can be used to find a $\ln n$ approximation for dominating set, which is known to be not possible. Therefore, I think that no $(c,2-\epsilon)$ bi-criteria approximation can exist for $c&lt;\ln n$.</p>

CC BY-SA 3.0
2014-08-22T20:19:13.353Z
2014-08-24T05:02:05.527Z
2014-08-24T05:02:05.527Z
Michael Lampis
<p>An $(\alpha, \beta)$ bi-criteria approximation algorithm for $k$-center is defined as an algorithm that returns a solution whose value is $\beta \cdot OPT$ ($OPT$ being the optimal solution for the $k$-center instance) using at most $\alpha \cdot k$ centers.</p>

<p>My question is: Given that finding a $(1,1)$bi-criteria approximation (which is basically just the optimal solution to the $k$-center problem, known to be $NP$-hard) is $NP$-hard, is it also true that finding a $(c, 1)$ bi-criteria approximation is $NP$-hard, where $c$ is a positive constant? </p>

<p>I've found that it is possible to have a $(\log k, 1)$ approximation for $k$-center, but not seen any negative results for a $(c, 1)$ bi-criteria approximation. I would appreciate if I can get pointers to a reference that I may have missed, or an outline of the proof sketch if its something trivial.</p>

<cc.complexity-theory><np-hardness><approximation-algorithms><approximation-hardness>
Inapproximability of $(\alpha, \beta)$ bi-criteria approximation
TCSGrad
# Inapproximability of $(\alpha, \beta)$ bi-criteria approximation

(Asked by: username_0 on 2014-08-22)

An $(\alpha, \beta)$ bi-criteria approximation algorithm for $k$-center is defined as an algorithm that returns a solution whose value is $\beta \cdot OPT$ ($OPT$ being the optimal solution for the $k$-center instance) using at most $\alpha \cdot k$ centers.

My question is: Given that finding a $(1,1)$bi-criteria approximation (which is basically just the optimal solution to the $k$-center problem, known to be $NP$-hard) is $NP$-hard, is it also true that finding a $(c, 1)$ bi-criteria approximation is $NP$-hard, where $c$ is a positive constant?

I've found that it is possible to have a $(\log k, 1)$ approximation for $k$-center, but not seen any negative results for a $(c, 1)$ bi-criteria approximation. I would appreciate if I can get pointers to a reference that I may have missed, or an outline of the proof sketch if its something trivial.

**Tags:** cc.complexity-theory, np-hardness, approximation-algorithms, approximation-hardness


---

## 1 answers

### Answer by username_1 on 2014-08-22. Score: 6 | Accepted answer

This problem generalizes dominating set: given an unweighted graph, there exists a set of k centers such that all other vertices are at distance 1 from them if and only if there exists a dominating set of size k.

Dominating set is hard to approximate with a ratio better than $\ln n$. In the above observation the optimal value for the k-center problem is either 1 or at least 2. Let $A$ be a $(c,2-\epsilon)$ bi-criteria approximation for $k$-center for some $c < \ln n$. If a dominating set of size $k$ exists, then the corresponding $k$-center problem would have optimum cost of 1, and $A$ would return a solution of cost at most $2-\epsilon$ using at most $k \ln n$ centers. Thus, $A$ can be used to find a $\ln n$ approximation for dominating set, which is known to be not possible. Therefore, I think that no $(c,2-\epsilon)$ bi-criteria approximation can exist for $c<\ln n$.


---

