K Centers Problem

Problem

Given n cities and distances between every pair of cities, select k cities to place warehouses (or ATMs, cloud servers, etc.) such that the maximum distance of any city to its nearest warehouse is minimized.

Examples

Example 1

$$ \begin{array}{|c|cccc|} \hline & 0 & 1 & 2 & 3 \\ \hline 0 & 0 & 4 & 7 & 6 \\ 1 & 4 & 0 & 8 & 5 \\ 2 & 7 & 8 & 0 & 7 \\ 3 & 6 & 5 & 7 & 0 \\ \hline \end{array} $$

graph TB;
	subgraph S1[" "]
		A
		D
	end
	
	subgraph S2[" "]
		B
		C
	end
A(1) ---|10| B(0)
A ---|5| C(3)
A ---|8| D(2)

B ---|7| D
B ---|6| C

D ---|12| C

S1 ~~~ S2

1
2
3
4
5
6
7
8
9


Input:
dist = [
	[0, 4, 7, 6],
	[4, 0, 8, 5],
	[7, 8, 0, 7],
	[6, 5, 7, 0]
], k = 2
Output: [0, 1] (or any valid set of 2 centers)
Explanation: There are 3 cities - 0, 1, 2 and 3. Placing centers at 0 and 1 minimizes the maximum distance from any city to a center.

Solution

Method 1 – Greedy 2-Approximation Algorithm

Intuition

Since the problem is NP-hard, we use a greedy algorithm that guarantees the maximum distance from any city to a center is at most twice the optimal. At each step, pick the city farthest from any chosen center as the next center.

Approach

Choose the first center arbitrarily.
For each of the remaining k-1 centers:

For each city not yet chosen as a center, compute its distance to the nearest chosen center.
Select the city with the maximum such distance as the next center.

After k centers are chosen, the maximum distance from any city to its nearest center is at most twice the optimal.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
public:
  std::vector<int> kCenters(const std::vector<std::vector<int>>& dist, int k) {
    int n = dist.size();
    std::vector<int> centers;
    std::vector<int> minDist(n, INT_MAX);
    centers.push_back(0); // pick first arbitrarily
    for (int i = 1; i < k; ++i) {
      for (int v = 0; v < n; ++v) {
        for (int c : centers) minDist[v] = std::min(minDist[v], dist[v][c]);
      }
      int next = -1, maxD = -1;
      for (int v = 0; v < n; ++v) {
        if (std::find(centers.begin(), centers.end(), v) == centers.end() && minDist[v] > maxD) {
          maxD = minDist[v];
          next = v;
        }
      }
      centers.push_back(next);
    }
    return centers;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution {
  public List<Integer> kCenters(int[][] dist, int k) {
    int n = dist.length;
    List<Integer> centers = new ArrayList<>();
    int[] minDist = new int[n];
    Arrays.fill(minDist, Integer.MAX_VALUE);
    centers.add(0);
    for (int i = 1; i < k; i++) {
      for (int v = 0; v < n; v++)
        for (int c : centers) minDist[v] = Math.min(minDist[v], dist[v][c]);
      int next = -1, maxD = -1;
      for (int v = 0; v < n; v++) {
        if (!centers.contains(v) && minDist[v] > maxD) {
          maxD = minDist[v];
          next = v;
        }
      }
      centers.add(next);
    }
    return centers;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
  def k_centers(self, dist: list[list[int]], k: int) -> list[int]:
    n = len(dist)
    centers = [0]
    min_dist = [float('inf')] * n
    for _ in range(1, k):
      for v in range(n):
        min_dist[v] = min([dist[v][c] for c in centers])
      next_city = max((d, v) for v, d in enumerate(min_dist) if v not in centers)[1]
      centers.append(next_city)
    return centers

Complexity

⏰ Time complexity: O(kN^2), where N is the number of cities and k is the number of centers. Each step checks all cities and all centers.
🧺 Space complexity: O(N), for the minDist array and centers list.

Problem#

Examples#

Example 1#

Solution#

Method 1 – Greedy 2-Approximation Algorithm#

Intuition#

Approach#

Code#

Complexity#