1
$\begingroup$

Consider the $k$-center problem where we are given an undirected, complete graph $G=(V, E)$, with a distance $d(u, v) \geq 0$ for each pair $u, v \in V$. Furthermore, we assume that the triangle inequality holds: for each triple $u, v, w \in V$ it is the case that $d(u, w) \leq d(u, v)+d(v+w)$. The goal is to find $k$ clusters, grouping together the vertices that are most similar into clusters together. The goal is to choose a set $S \subseteq V$ of $k$ cluster centers such that we minimize the maximum distance of a vertex to its cluster center.

It is not difficult to show that there is no $\rho$-approximation algorithm for the $k$-center problem for $\rho < 2$ unless $\mathbf{P}=\mathbf{NP}$: Consider the dominating set problem, which is NP-complete. In the dominating set problem, we are given a graph $G = (V, E)$ and an integer $k$, and we must decide if there exists a set $S ⊆ V$ of size $k$ such that each vertex is either in $S$, or adjacent to a vertex in $S$. Given the instance $G=(V, E)$ of the dominating set problem, we can then construct an instance $G'=(V, E')$ of the $k$-center problem by setting the distance between adjacent vertices in $G$ to 1 in $G'$, and the distances between nonadjacent vertices in $G$ to 2 in $G'$. Then, there is a dominating set of size $k$ if and only if the optimal distance ($OPT$) for $k$-cluster instance $G'$ is $1$. Thus, if we assume we have an approximation algorithm $A$ for the $k$-center problem with approximation factor $\rho < 2$, we can run it on $G'$. Then, if $OPT=1$, $A$ will return a solution with distance $<2$, i.e. 1. Else, if $OPT =2$, $A$ will return a solution with distance at least $2$. Thus, we can solve the dominating set decision problem, which implies that $\mathbf{P}=\mathbf{NP}$.

My question is then concerned with the $c$-relaxed $k$-center problem, where we do not have a metric but only the following approximate triangle inequality: For each triple $u, v, w \in V$, it is the case that $d(u, w)/c \leq d(u, v)+d(v, w)$. Is it possible to show that unless $\mathbf{P}=\mathbf{NP}$, there is no solution to the $c$-relaxed $k$-center problem with approximation factor $\rho < c+1$

$\endgroup$

1 Answer 1

1
$\begingroup$

You can show hardness of approximation of any $\rho < 2c$.

Simply take the distance between non-adjacent vertices to be $2c$ and distance between the adjacent vertices to be $1$. Note that the graph should satisfy relaxed triangle-inequality, and it indeed does, given that $c \geq 1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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