K-Centers (Greedy 2-Approximation)

K-Centers is a classic facility-location problem and a beautiful introduction to approximation algorithms. The exact answer is NP-hard, but a dead-simple greedy rule gets you within a factor of 2 of optimal — and that bound is provably the best any polynomial algorithm can guarantee.

The slow way first

The exact solution means trying every way to choose k of the n points — that is C(n, k) subsets, exponential in k. For each subset you would also recompute every point distance. This is NP-hard: there is no known polynomial algorithm that finds the true optimum, so for any real-sized input we cannot brute-force it.

The question to ask: can we get close to optimal, fast? For K-Centers the answer is a clean yes — a greedy heuristic gives a 2-approximation in near-linear time.

The idea: always grab the worst-served point

Build the center set one at a time. Pick an arbitrary first center. Then repeat: look at every point, find the one currently farthest from its nearest chosen center, and make that point the next center. Do this until you have k centers.

The intuition is greedy fairness: the point hurting your covering radius the most is exactly the one screaming for its own center, so you give it one.

The key insight: keep a running array d[p] of each point's distance to its nearest center. After adding a new center, you only need to relax d against the new center — no full recompute — so each round is O(n).

Walk through it

Step through the animation. We start with center 0; the number under each point is its distance to the nearest center. The farthest pointer jumps to the point with the biggest distance, which becomes the next center. After two more picks we hold three centers, and the covering radius has shrunk from 20 down to 5.

Pseudocode

centers = [arbitrary point, say 0]
d[p] = distance(p, 0) for every point p     # nearest-center distance so far
while we have fewer than k centers:
    far = the point p with the largest d[p]
    add far to centers
    for every point p:
        d[p] = min(d[p], distance(p, far))  # relax against the new center
return max(d)                                # the covering radius

The Python solution

def k_centers(points, k, dist):
    centers = [0]
    d = [dist(p, 0) for p in range(len(points))]
    while len(centers) < k:
        far = max(range(len(points)), key=lambda p: d[p])
        centers.append(far)
        for p in range(len(points)):
            d[p] = min(d[p], dist(p, far))
    return max(d)

• centers = [0] seeds the set with an arbitrary first center; the 2-approximation holds no matter which point you start from.
• d holds each point's distance to its nearest center seen so far — initially everyone measures to center 0.
• far = max(... key=lambda p: d[p]) is the greedy choice: the worst-served point.
• After appending far, the inner loop relaxes d — each point keeps the smaller of its old distance and its distance to the new center. That is the O(n) update that avoids a full recompute.
• return max(d) is the final covering radius.

Complexity

The greedy method runs in O(nk) and stores one distance per point. Its covering radius is provably at most twice the optimal — and no polynomial algorithm can guarantee better than 2× unless P = NP.

When this pattern shows up

Practice