4
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.