The design of Approximation Algorithm: Exercises 2.1. (a)

The k-suppliers problem is similar to the k-center problem given in Section 2.2. 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 Subsetequalto V and customers D = V - 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 Subsetequalto F, |S| lessthanorequalto k, that minimizes max_j elementof D d(j, S). (a) Give a 3-approximation algorithm for the k-suppliers