# Solve K Centers problem in Python

Hi everyone, in this tutorial we are going to discuss the K Centers problem in Python and see how we can solve it.

In brief, we can be called K Centers as Metric k Center problem which is an NP-Hard Problem.

Given p dots, we need to choose k (k<=p) centers, such that the maximum distance of a dot to the center is minimized. In layman terms, say we need to build k warehouses given a map of p connected dots. The best way to build a warehouse is by keeping in mind that, it must be closest to the dots. In other words, the maximum distance of a dot to the warehouse must be minimal.

First of all, take a look at an example of the K Center image.

Now we will be looking at a greedy approach towards this problem

- Pick an arbitrary center, p1.
- For every remaining dots P
_{1}, P_{2},… P_{N-}, compute the minimum distance from the centers chosen already. - Pick the new center with the highest distance from already chosen centers, that is max((dist(p
_{1}, P_{1}), dist(p_{1},P_{2}), … dist(p_{1}, p_{N-1})). - Continue this procedure until all the k centers are found.

Here is one of the important factors that we need to understand that this greedy approach has an approximate factor 2.

## Code in Python for K Center problem

Below is our Python program:

import networkx as pt import matplotlib.pyplot as pst import operator def k_centers_prob(V, n): centers = [] cities = V.nodes() centers.append((V.nodes())[0]) cities.remove(centers[0]) n = n-1 while n!= 0: city_dict = {} for cty in cities: min_dist = float("inf") for c in centers: min_dist = min(min_dist,V[cty][c]['length']) city_dict[cty] = min_dist new_center = max(city_dict, key = lambda i: city_dict[i]) centers.append(new_center) cities.remove(new_center) n = n-1 return centers def cGraph(): V = pt.Graph() f = open('input.txt') n = int(f.readline()) wtMatrix = [] for i in range(n): list1 = map(int, (f.readline()).split()) wtMatrix.append(list1) for i in range(n) : for j in range(n)[i:] : V.add_edge(i, j, length = wtMatrix[i][j]) noc = int(f.readline()) return V, noc def dGraph(V, centers): pos = pt.spring_layout(V) color_map = ['blue'] * len(V.nodes()) for c in centers: color_map[c] = 'red' pt.draw(V, pos, node_color = color_map, with_labels = True) edge_labels = pt.get_edge_attributes(V, 'length') pt.draw_networkx_edge_labels(V, pos, edge_labels = edge_labels, font_size = 11) #main function if __name__ == "__main__": V,n = cGraph() c = k_centers_prob(V, n) dGraph(V, centers) pst.show()

Input: 4 0 10 7 6 10 0 8 5 7 8 0 2 6 5 12 0 3

You can also be referred to:

## Leave a Reply

You must be logged in to post a comment.