The algorithm is about k-mean center problem. In the algorithm for the k-center problem, the first cluster head is chosen randomly. A naïve improvement is to try every node as the first cluster head and then find the corresponding partition. Therefore, we obtain n = |V| partitions. Finally, we simply output the best partition among these n partitions, i.e., the one that has the smallest maximum radius. This program actually compare the original greedy algorithm and the above naïve improvement. The first output graph is of greedy algorithm and the remaining are from forced selection of nodes. first we select node 1 then node 2 and so on. if the graph has 10 vertices, v1, v2, …, v10, then the first cluster head chosen by Greedy can be any of these 10 vertices. A naïve improvement is the following: We force the algorithm to choose v1 as the first cluster head and obtain a corresponding solution S1. We can also force ALG to choose v2 as the first cluster head and obtain a corresponding solution S2. Therefore, we can obtain 10 solutions S1, S2, …, S10. Finally, the naïve improvement simply outputs the best one among these 10 solutions, i.e., the one that has the minimum radius.

For details refer to the Greedy_naive.pdf