K Centers Problem

The problem, simply

You get n cities and the distance between every pair (for a road map, the shortest road distance). You may build k centers, for example fire stations, each in one of the cities.

Every city goes to its nearest center. Choose the centers so that the worst distance, the distance of the city that is farthest from its nearest center, is as small as possible. Give back that worst distance (called the radius).

Finding the exact best is very hard for big inputs: nobody knows a fast method. So the classic answer is a greedy that is fast and guaranteed to be at most twice the best.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every group of k cities as centers. For each group, find every city's nearest center, take the worst, and keep the group with the smallest worst.

class Solution {
    private int best;

    public int kCenters(int[][] dist, int k) {
        int n = dist.length;
        best = Integer.MAX_VALUE;
        choose(dist, Math.min(k, n), 0, new ArrayList<>());
        return best;
    }

    private void choose(int[][] dist, int k, int start, List<Integer> centers) {
        if (centers.size() == k) {
            int worst = 0;
            for (int city = 0; city < dist.length; city++) {
                int near = Integer.MAX_VALUE;
                for (int c : centers) near = Math.min(near, dist[city][c]);
                worst = Math.max(worst, near);           // the longest walk in this plan
            }
            best = Math.min(best, worst);
            return;
        }
        for (int i = start; i < dist.length; i++) {
            centers.add(i);
            choose(dist, k, i + 1, centers);
            centers.remove(centers.size() - 1);
        }
    }
}

How long it takes: C(n, k) groups, each checked in O(n * k), so O(C(n, k) * n * k). Extra room: O(k). This gives the exact best, but only for small towns.

Way 2: the clever way

The farthest first greedy.

1. Pick any city as the first center. Set near[i] to the distance from city i to it.
2. Repeat until you have k centers: the city with the biggest near is the worst off. Make it a center. Then for every city, near[i] = min(near[i], dist[i][new center]).
3. The answer is the biggest near at the end.

Why is it at most twice the best? Suppose the best plan has radius r, and greedy ends with some city x still more than 2r away. Then the k greedy centers and x are all more than 2r apart from each other (each was the worst off when picked). That is k + 1 cities, so two of them share a center in the best plan, and by the triangle rule they are at most 2r apart. That is a contradiction. The proof needs distances that obey the triangle rule, which shortest road distances do.

class Solution {
    public int kCenters(int[][] dist, int k, List<Integer> centers) {
        int n = dist.length;
        int[] near = new int[n];
        centers.add(0);                                   // any city can be first
        for (int i = 0; i < n; i++) near[i] = dist[i][0];

        while (centers.size() < Math.min(k, n)) {
            int far = 0;
            for (int i = 1; i < n; i++) if (near[i] > near[far]) far = i;  // worst off city
            centers.add(far);
            for (int i = 0; i < n; i++) near[i] = Math.min(near[i], dist[i][far]);
        }

        int radius = 0;
        for (int d : near) radius = Math.max(radius, d);
        return radius;
    }
}

How long it takes: k rounds, each scanning n cities twice, O(n * k), once the distance table is ready. If you start from a road map, building the table with Floyd Warshall costs O(n^3). Extra room: the near array, O(n).

Watch out for

• Use shortest path distances, not only the road lengths that happen to exist. The guarantee needs the triangle rule.
• If k >= n, every city gets a center and the answer is 0. Stop the loop at min(k, n).
• The result depends on the first city. Trying every city as the first and keeping the best is a cheap improvement, O(n^2 * k).
• A city that is already a center has near = 0, so it is never picked twice.

What interviewers ask next

• Can anyone do better than twice the best quickly? No. Unless P equals NP, no fast method promises better than a factor of 2.
• How do you get the exact answer for medium sizes? Binary search on the radius over the sorted distinct distances. For a radius r, ask whether k centers can cover every city within r. That check is a set cover question, solved with an integer program or a careful search.
• What is the version on a line or on a tree? On a line, sort the points, binary search the radius, and greedily place a center as far right as it can go while still covering the leftmost uncovered point. That is exact and fast.
• How is this used in practice? Choosing cluster centers (it is a way to seed k means), placing servers or warehouses, and picking a diverse sample of points.

Remember this

Grown-up words: the trucks are centers, the longest walk is the covering radius, picking the worst off city is farthest first traversal (Gonzalez's algorithm), "at most twice the best" is a 2 approximation, and "nobody knows a fast exact method" is NP hardness.