10.2. Inapproximability of Metric \(k\)-Center

The metric \(k\)-center problem is the only problem for which we prove that the algorithm we developed is essentially optimal, as stated by the following theorem:

Theorem 10.4: Assuming that \(\textrm{P} \ne \textrm{NP}\) and \(\epsilon > 0\) is a constant, there exists no polynomial-time algorithm that computes a \((2-\epsilon)\)-approximation of an optimal solution to the metric \(k\)-center problem.

Proof: Again, we use the close relationship between the \(k\)-center problem and the dominating set problem. We prove that any polynomial-time \((2-\epsilon)\)-approximation algorithm for the metric \(k\)-center problem can be used to solve the dominating set problem in polynomial time. Since the dominating set problem is NP-hard, this is impossible unless \(\textrm{P} = \textrm{NP}\).

So consider any graph \(G\) for which we want to decide whether it has a dominating set of size \(k\). We construct a complete graph \(K\) with the same vertex set as \(G\). An edge in \(K\) has weight \(1\) if it is an edge of \(G\), and weight \(2\) otherwise. These edge weights clearly satisfy the triangle inequality. Now we run the \((2-\epsilon)\)-approximation algorithm for the metric \(k\)-center problem on \(K\). If the computed solution has an objective function value less than \(2\), we report it as a dominating set of \(G\) of size \(k\). Otherwise, we report that \(G\) has no dominating set of size \(k\).

This algorithm clearly takes polynomial time because the construction of \(K\) from \(G\) can trivially be carried out in polynomial time and we assumed that there exists a polynomial-time \((2-\epsilon)\)-approximation algorithm for the metric \(k\)-center problem. We have to prove that the algorithm is a correct algorithm for the dominating set problem.

If we find a solution \(C\) of the metric \(k\)-center problem with an objective function value less than \(2\), then its objective function value is in fact \(1\) because all edges in \(K\) have weight \(1\) or \(2\). Thus, every vertex \(x \in V \setminus C\) is connected to a vertex \(y \in C\) by an edge \((x,y)\) of weight \(1\). Since every weight-\(1\) edge of \(K\) is an edge of \(G\), this shows that \(y\) dominates \(x\) in \(G\). Since this is true for all \(x \in V \setminus C\), \(C\) is a dominating set of \(G\). Its size is \(k\) because \(C\) is a solution of the metric \(k\)-center problem.

Conversely, assume that \(G\) has a dominating set \(D\) of size \(k\). Then every vertex \(x \notin D\) has a neighbour \(y \in D\). In \(K\), the edge \((x,y)\) has weight \(1\), so \(\min_{y' \in D} w_{x,y'} \le w_{x,y} \le 1\) for every vertex \(x \notin D\), and \(\max_{x \in V \setminus D} \min_{v' \in D} w_{x,y'} \le 1\). The \((2 - \epsilon)\)-approximation algorithm for the metric \(k\)-center problem thus returns a solution with objective function value at most \(2 - \epsilon < 2\). This proves that if the algorithm does not find a set of centers with an objective function value less than \(2\), then \(G\) has no dominating set of size \(k\). ▨

Exercise 10.3: The \(k\)-center problem is closely related to the \(k\)-clustering problem, which is one way to formulate the problem of clustering a set of data points into \(k\) clusters, a problem central to many techniques in machine learning. In the \(k\)-clustering problem, we are once again given an edge-weighted complete graph \(G\). Our goal is to partition the vertex set of \(G\) into \(k\) subsets \(V_1, \ldots, V_k\), the clusters, so that the weight of the heaviest edge between two vertices in the same cluster is minimized. Formally, we want to minimize

\[w(V_1, \ldots, V_k) = \max_{1 \le i \le k} \max_{u,v \in V_i} w(u,v).\]

• Prove that this problem has no polynomial-time \(\alpha(n)\)-approximation algorithm for any polynomial-time computable function \(\alpha\) unless the weight function \(w\) is a metric—that is, unless the edge weights satisfy the triangle inequality—or \(\textrm{P} = \textrm{NP}\).
• Provide a polynomial-time \(2\)-approximation for the metric \(k\)-clustering problem.
• Prove that the metric \(k\)-clustering problem has no polynomial-time \((2 - \epsilon)\)-approxi-mation algorithm, for any constant \(\epsilon > 0\), unless \(\textrm{P} = \textrm{NP}\).

(Hint: The constructions in this exercise are very similar to the constructions for the metric \(k\)-center problem; they are in fact a little easier. Both the \(2\)-approximation algorithm for metric \(k\)-center and the inapproximability results rely on the close relationship between the \(k\)-center problem and the dominating set problem. For the \(k\)-clustering problem, the clique cover problem plays the role of the dominating set problem. The clique cover problem asks whether there exists a partition of the vertex set of a graph \(G\) into \(k\) subsets \(V_1, \ldots, V_k\) such that the induced subgraph \(G[V_i]\) is a clique, a complete graph over the vertex set \(V_i\), for all \(1 \le i \le k\).)