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₁, P₂,… 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₁, P₁), dist(p₁,P₂), … dist(p₁, 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()

You can also be referred to:

Solve K Centers problem in Python

Code in Python for K Center problem

Leave a Reply Cancel reply