Clustering is one of the key problems in machine learning and data science. Given a set of objects, the task is to partition these objects into groups such that objects within a group are more similar. In this exercise, we’ll design a 2-approximate algorithm for a specific clustering task called k-center. Given n vertices in the plane and a positive integer k, we’ll choose k cluster centers among the given n vertices. After that, every vertex will be assigned to its closest cluster center. The radius of such clustering is the maximum distance of a vertex to its center. In the k-center problem, the goal is to find k cluster centers that minimize the clustering radius. Consider the following greedy algorithm for this problem. First, pick any vertex as the first cluster center. Pick each of the remaining k ?1 cluster centers in the greedy way: choose a vertex whose minimum distance to the already selected centers is maximum. Prove that the above algorithm is 2-approximate. In other words, prove that the radius of the clustering found by the greedy algorithm is at most two times larger than the optimal clustering radius. For this, consider two cases:
• Case 1: the greedy algorithm picked one cluster center from each cluster of an optimal solution.
• Case 2: the greedy algorithm picked at least two cluster centers from some cluster of an optimal solution