K Centers Problem

Problem Statement

Given n cities and their pairwise distances, select k cities as centers such that the maximum distance of any city from its nearest center is minimized.

This is a classic facility location problem where we want to place k facilities to minimize the worst-case distance for any city.

Constraints:

• 2 ≤ k ≤ n ≤ 1000
• Distances are non-negative

Example:

• Input: n=4, k=2, distances matrix for cities at positions [0, 2, 6, 8] on a line
• Output: Centers at cities 0 and 2 or 2 and 3, minimizing max distance

Example 2:

• Input: n=5, k=2, cities in a graph
• Output: Select 2 centers minimizing the maximum distance to nearest center

Approach 1: Brute Force (Try All Combinations)

Intuition

Try all possible combinations of k centers from n cities. For each combination, calculate the maximum distance from any city to its nearest center. Return the minimum over all combinations.

Algorithm

1. Generate all C(n, k) combinations of centers
2. For each combination, calculate max(min distance to any center)
3. Track and return the minimum maximum distance

import java.util.*;

public class Solution {
    private int minMaxDistance = Integer.MAX_VALUE;
    
    public int kCenters(int[][] dist, int n, int k) {
        minMaxDistance = Integer.MAX_VALUE;
        findCombinations(dist, n, k, 0, new ArrayList<>());
        return minMaxDistance;
    }
    
    private void findCombinations(int[][] dist, int n, int k, int start,
                                   List<Integer> centers) {
        if (centers.size() == k) {
            int maxDist = 0;
            for (int i = 0; i < n; i++) {
                int minDist = Integer.MAX_VALUE;
                for (int c : centers) {
                    minDist = Math.min(minDist, dist[i][c]);
                }
                maxDist = Math.max(maxDist, minDist);
            }
            minMaxDistance = Math.min(minMaxDistance, maxDist);
            return;
        }
        
        for (int i = start; i < n; i++) {
            centers.add(i);
            findCombinations(dist, n, k, i + 1, centers);
            centers.remove(centers.size() - 1);
        }
    }
}

Complexity Analysis

• Time Complexity: O(n^k × n) - C(n,k) combinations, each checked in O(n)
• Space Complexity: O(n) - For storing centers

Approach 2: Greedy Farthest First Traversal (Approximation)

Intuition

This is a 2-approximation algorithm for the k-center problem:

1. Start with an arbitrary city as the first center
2. Repeatedly add the city that is farthest from all current centers
3. Continue until we have k centers

Why 2-approximation? The solution is guaranteed to be at most 2× the optimal solution.

Algorithm

1. Pick first center arbitrarily (or the one with max sum of distances)
2. For i = 2 to k:
   • Find city with maximum distance to nearest center
   • Add it as a new center
3. Return the final maximum distance

import java.util.*;

public class Solution {
    public int[] kCentersGreedy(int[][] dist, int n, int k) {
        boolean[] isCenter = new boolean[n];
        List<Integer> centers = new ArrayList<>();
        int[] minDistToCenter = new int[n];
        Arrays.fill(minDistToCenter, Integer.MAX_VALUE);
        
        // Start with city 0
        isCenter[0] = true;
        centers.add(0);
        for (int i = 0; i < n; i++) {
            minDistToCenter[i] = dist[i][0];
        }
        
        // Add k-1 more centers
        for (int c = 1; c < k; c++) {
            int farthest = -1;
            int maxDist = -1;
            
            for (int i = 0; i < n; i++) {
                if (!isCenter[i] && minDistToCenter[i] > maxDist) {
                    maxDist = minDistToCenter[i];
                    farthest = i;
                }
            }
            
            isCenter[farthest] = true;
            centers.add(farthest);
            
            for (int i = 0; i < n; i++) {
                minDistToCenter[i] = Math.min(minDistToCenter[i], dist[i][farthest]);
            }
        }
        
        int maxDist = 0;
        for (int d : minDistToCenter) {
            maxDist = Math.max(maxDist, d);
        }
        
        int[] result = new int[k + 1];
        result[0] = maxDist;
        for (int i = 0; i < k; i++) {
            result[i + 1] = centers.get(i);
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] dist = {
            {0, 2, 6, 8},
            {2, 0, 4, 6},
            {6, 4, 0, 2},
            {8, 6, 2, 0}
        };
        int[] result = sol.kCentersGreedy(dist, 4, 2);
        System.out.println("Max distance: " + result[0]);
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n² × k) - For each of k centers, we scan n cities and update n distances
• Space Complexity: O(n) - For distance tracking

Approach 3: Binary Search + Dominating Set (Optimal)

Intuition

Binary search on the maximum distance. For each candidate distance d, check if we can select at most k centers such that every city is within distance d of some center.

Algorithm

1. Collect all unique distances and sort them
2. Binary search on the maximum distance
3. For each candidate, check if k centers suffice using a greedy approach

Complexity Analysis

• Time Complexity: O(n² log n) - Binary search over O(n²) distances, each check is O(n)
• Space Complexity: O(n²) - For storing all distances

Key Takeaways

1. NP-Hard Problem: K-center is NP-hard to solve optimally
2. 2-Approximation: Greedy farthest-first achieves 2× optimal
3. Farthest First: Always pick the city farthest from all centers
4. Binary Search: Can search on answer space with feasibility check
5. Practical Applications: Facility location, network design, clustering
6. Vertex Cover Connection: Related to dominating set problems
7. Metric Property: Assumes triangle inequality for distance