The design of Approximation Algorithm: Exercises 2.1. (a) The k-suppliers proble
ID: 3870294 • Letter: T
Question
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 problem.Explanation / Answer
1.Choose the first center arbitrarily in this case say i.
2. At every step, choose the vertex that is furthest from the current centers to become a center
3 Continue until k centers are chosen