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, kk, and a set of vertices VV, along with distances dijd_{ij} between any two vertices, i,ji,j that obey the same properties as in the k-center problem. However, now the vertices are partitioned into suppliers FVF \subseteq V and customers D=VFD = V \setminus F. The goal is to find kk suppliers such that the maximum distance from a supplier to a customer is minimized. In other words, we wish to find SF,SkS \subseteq F, |S| \leq k, that minimizes maxjDd(j,S)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 α<3\alpha < 3 unless P = NP.
1

Answers

1. That algorithm starts by choosing a supplier that is closest to an arbitrary customer, then in each of the following k1k-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 D1,,DkD_1, \dots, D_k with its corresponded suppliers f1,,fkf^*_1, \dots, f^*_k. Now suppose that the algorithm chooses a customer from each of these groups, d1,,dkd_1, \dots, d_k and its corresponded suppliers f1,,fkf_1, \dots, f_k, let cic_i be a customer in the iith group, then from the triangle inequality it follows that:

d(ci,fi)d(ci,di)+d(di,fi)2(ci,fi)+d(di,fi)3OPT 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 OPTOPT is the value of an optimal solution.

On the other hand, if the algorithm chooses 2 customers from the same group, di,eid_i, e_i and let cjc_j be a customer in the jjth (j>ij > i) group, then it follows that:

d(cj,fj)d(ei,fi)d(ei,di)+d(di,fi)2d(ei,fi)+d(di,fi)3OPT. 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 α<3\alpha < 3 unless P = NP consider an instance of the set cover problem ({e1,,en},{S1,,Sm},k)(\{e_1, \dots, e_n\}, \{S_1, \dots, S_m\}, k) and consider the metric space d(Si,Sj)=d(ek,el)=2d(S_i, S_j) = d(e_k, e_l) = 2 and d(Si,ej)=1,ejSi,d(Si,ej)=3,ej/Sid(S_i, e_j) = 1, e_j \in S_i, d(S_i, e_j) = 3, e_j \notin S_i, then for F={S1,,Sm}F = \{S_1, \dots, S_m\} and D={e1,,en}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