### Question

greedy
hardness
k-center
k-suppliers

The k-suppliers problem is similar to the k-center problem. The input to the problem is a positive integer, $k$, and a set of vertices $V$, along with distances $d_{ij}$ between any two vertices, $i,j$ that obey the same properties as in the k-center problem. However, now the vertices are partitioned into suppliers $F \subseteq V$ and customers $D = V \setminus F$. The goal is to find $k$ suppliers such that the maximum distance from a supplier to a customer is minimized. In other words, we wish to find $S \subseteq F, |S| \leq k$, that minimizes $max_{j \in D}d(j, S)$.

1. Give a 3-approximation algorithm for the k-suppliers problem.
2. Prove that there is no $\alpha$-approximation algorithm for $\alpha < 3$ unless P = NP.
1

1. That algorithm starts by choosing a supplier that is closest to an arbitrary customer, then in each of the following $k-1$ iterations it chooses the supplier that is closest to the furthest customer from the currently selected suppliers.

Claim: The above algorithm is 3-approximation algorithm for the k-suppliers problem.

Proof: Consider the k groups of customers induced by an optimal solution $D_1, \dots, D_k$ with its corresponded suppliers $f^*_1, \dots, f^*_k$. Now suppose that the algorithm chooses a customer from each of these groups, $d_1, \dots, d_k$ and its corresponded suppliers $f_1, \dots, f_k$, let $c_i$ be a customer in the $i$th group, then from the triangle inequality it follows that:

$d(c_i, f_i) \leq d(c_i, d_i) + d(d_i, f_i) \leq 2(c_i, f^*_i) + d(d_i, f^*_i) \leq 3OPT$

where $OPT$ is the value of an optimal solution.

On the other hand, if the algorithm chooses 2 customers from the same group, $d_i, e_i$ and let $c_j$ be a customer in the $j$th ($j > i$) group, then it follows that:

$d(c_j, f_j) \leq d(e_i, f_i) \leq d(e_i, d_i) + d(d_i, f_i) \leq 2d(e_i, f^*_i) + d(d_i, f^*_i) \leq 3OPT.$

2. To show that there is no $\alpha$-approximation algorithm for $\alpha < 3$ unless P = NP consider an instance of the set cover problem $(\{e_1, \dots, e_n\}, \{S_1, \dots, S_m\}, k)$ and consider the metric space $d(S_i, S_j) = d(e_k, e_l) = 2$ and $d(S_i, e_j) = 1, e_j \in S_i, d(S_i, e_j) = 3, e_j \notin S_i$, then for $F = \{S_1, \dots, S_m\}$ and $D = \{e_1, \dots, e_n\}$ there are k suppliers with distance 1 from D $\iff$ there is a set cover of size k.

1
Feedback