10.3. Weighted Metric \(\boldsymbol{k}\)-Center

The weighted metric \(k\)-center problem is an extension of the metric \(k\)-center problem that models that adding different vertices to the set of centers may incur different costs. For example, looking at the metric \(k\)-center problem as a facility location problem again, the cost of building a store at different locations may differ depending on the terrain and type of soil found there, so if we want to stay on budget, then we cannot simply open \(k\) arbitrary stores; we need to open a set of stores that does not exceed our budget.

Weighted Metric \(\boldsymbol{k}\)-Center Problem: Given an undirected graph \(G = (V, E)\), a weight function \(w : E \rightarrow \mathbb{R}\), a cost function \(c : V \rightarrow \mathbb{R}^+\), and a positive budget \(B\), choose a set of centers \(C \subseteq V\) such that

\[\sum_{y \in C} c_y \le B\]

and

\[\max_{x \in V \setminus C} \min_{y \in C} w_{x,y}\]

is minimized.

Our approach to solving the weighted metric \(k\)-center problem is very similar to the one we chose to solve the unweighted metric \(k\)-center problems. The main difference is that we cannot simply return the maximal independent set we found as a set of centers because the cost of the vertices in this independent set may exceed our budget. We will see that we can replace each vertex in the independent set with a neighbour of low weight so that the vertices in the resulting set do not exceed our budget. However, this increases the approximation ratio from \(2\) to \(3\).

So we consider the same sequence of graphs \(G_1, \ldots, G_m\) as in the unweighted case, where \(e_1, \ldots, e_m\) is the sequence of edges in \(G\), sorted by increasing weights, and each graph \(G_j\) contains the \(j\) cheapest edges in \(G\): \(e_1, \ldots, e_j\).

In the unweighted case, the first crucial observation was that a subset \(C \subseteq V\) of size \(k\) is an optimal set of centers if and only if it is a dominating set of the graph \(G_{j^*}\), where \(j^*\) is the smallest index such that \(G_{j^*}\) has a dominating set of size \(k\). The adaptation to the weighted case is straightforward: Now we are looking for the smallest index \(j^*\) such that \(G_{j^*}\) has a dominating set of cost at most \(B\). The proof of the following lemma is almost identical to the proof of Lemma 10.1, so we state it without proof:

Lemma 10.5: \(\mathrm{OPT} = w_{e_{j^*}}\), where \(j^*\) is the minimum index such that \(G_{j^*}\) has a dominating set of cost at most \(B\).

Finding such a dominating set or even a good approximation, on the other hand, is harder. Consider a graph \(G_j\) and its square \(G_j^2\). Let \(I\) be an independent set of \(G_j^2\). We associate a set of centers \(C_I\) with \(I\), which includes the cheapest neighbour in \(G_j\) of every vertex \(y \in I\):

\[C_I = \bigl\{n^j_y \mid y \in I\bigr\},\]

where \(n^j_y\) is an arbitrary vertex such that

• \(G_j\) contains the edge \((y, n^j_y)\) and
• \(n^j_y\) has minimum cost among all vertices meeting the previous condition.

Just as we were able to prove that \(G_j\) has no dominating set of size \(k\) if \(G_j^2\) has an independent set of size greater than \(k\), the following lemma shows that \(G_j\) has no dominating set of cost at most \(B\) if \(G_j^2\) has an independent set \(I\) whose corresponding set of centers \(C_I\) has a cost exceeding \(B\):

Lemma 10.6: For any dominating set \(D\) of \(G_j\) and any maximal independent set \(I\) of \(G_j\), we have \(c(C_I) \le c(D)\).

Proof: Let \(I = \{x_1, \ldots, x_s\}\) and \(D = \{y_1, \ldots, y_t\}\). Since \(D\) is a dominating set, every vertex \(x_i \in I\) has a neighbour \(y_{j_i} \in D\). Since \(n^j_{x_i}\) is the cheapest neighbour of \(x_i\) in \(G_j\), we have \(c_{n^j_{x_i}} \le c_{y_{j_i}}\). Thus,

\[c(C_I) \le \sum_{i=1}^s c_{n^j_{x_i}} \le \sum_{i=1}^s c_{y_{j_i}}.\]

The first inequality is not necessarily an equality because multiple vertices in \(I\) may share the same cheapest neighbour. This vertex is included in \(C_I\) only once but is counted more than once in the sum \(\sum_{i=1}^s c_{n^j_{x_i}}\).

It remains to prove that

\[c(D) \ge \sum_{i=1}^s c_{y_{j_i}}.\]

In particular, we need to argue that there is no vertex \(y \in D\) that is adjacent to two vertices \(x_h\) and \(x_i\) in \(I\) because this vertex would be counted only once in \(c(D)\) but would contribute multiple times to the sum \(\sum_{i=1}^s c_{y_{j_i}}\).

This is easy to show: If there were two vertices \(x_h\) and \(x_i\) in \(I\) that share a common neighbour \(y\) in \(D\), then \(x_h\) and \(x_i\) would be adjacent in \(G_j^2\). Thus, they would not both be included in \(I\) because \(I\) is an independent set of \(G_j^2\). ▨

Based on this lemma, we can now formulate a \(3\)-approximation algorithm for the weighted metric \(k\)-center problem:

• For \(j = 1, \ldots, m\):

  • Compute \(G_j\) and then \(G_j^2\), find a maximal independent set \(I\) of \(G_j^2\), and then construct the set of centers \(C_I\) associated with \(I\). By Exercise 7.4, we can find \(I\) in polynomial time, and construcing \(C_I\) from \(I\) is easily accomplished in \(O(m)\) time.

  • If \(c(C_I) > B\), then \(G_j\) has no dominating set of cost at most \(B\), by Lemma 10.6. Thus, \(j < j^*\).

  • If \(c(C_I) \le B\), then we cannot guarantee that \(G_j\) has no dominating set of cost at most \(B\), so we also cannot guarantee that \(j < j^*\). In this case, we return the set \(C_I\) as a set of centers. Clearly, \(C_I\) has the desired cost of at most \(B\). By the next lemma, \(C_I\) is a \(3\)-approximation of an optimal set of centers of cost at most \(B\).

Lemma 10.7: \(\max_{x \notin V \setminus C_I} \min_{y \in C_I} w_{x,y} \le 3 \cdot \textrm{OPT}\).

Proof: Let \(j\) be the index of the iteration in which we return \(C_I\). Then \(j \le j^*\) because every index \(j' < j\) satisifes \(j' < j^*\). Thus, we have

\[w_{e_j} \le w_{e_{j^*}} = \textrm{OPT}\]

and it suffices to prove that

\[\max_{x \in V \setminus C_I}\min_{y \in C_I}w_{x,y} \le 3 w_{e_j}.\]

Consider any vertex \(x \notin C_I\). Then either \(x \in I\) or there exists a vertex \(z \in I\) such that \(x\) and \(z\) are neighbours in \(G^2_j\), because \(I\) is a maximal independent set of \(G_j^2\). In the case when \(x \in I\), we choose \(z = x\). Let \(y = n^j_z\). Note that \(y \in C_i\). Then we have \(w_{y,z} \le w_{e_j}\). Thus, if \(z = x\), then

\[\min_{y' \in C_I}w_{x,y'} \le w_{x,y} \le w_{e_j}.\]

If \(z \ne x\), then since \((x,z)\) is an edge of \(G_j^2\), \(x\) and \(z\) have a common neighbour \(v\) in \(G_j\). In particular, \(w_{x,v} \le w_{e_j}\) and \(w_{v,z} \le w_{e_j}\). Thus, by the triangle inequality, we have \(w_{x,z} \le w_{x,v} + w_{v,z} \le 2w_{e_j}\). Using the triangle inequality a second time, we obtain \(w_{x,y} \le w_{x,z} + w_{z,y} \le 3w_{e_j}\). This shows that

\[\min_{y' \in C_I}w_{x,y'} \le w_{x,y} \le w_{e_j}.\]

Since this is true for every vertex \(x \in V \setminus C_i\), we thus have

\[\max_{x \in V \setminus C_I}\min_{y \in C_i}w_{x,y} \le 3w_{e_j}.\ \text{▨}\]