Why Is the Greedy Algorithm Optimal for Set Cover?

Set cover asks for the fewest subsets, drawn from a given collection, whose union covers every element of a universe. It’s NP-hard, and it generalizes cleanly recognizable problems like scheduling and facility placement. The obvious heuristic is greedy: at each step, pick whichever remaining subset covers the most elements not yet covered, and repeat until done. The set-cover greedy approximation record tracks exactly how good that simple idea provably is — and how it compares to the best any algorithm could do.

A bound proven in the 1970s

Greedy’s worst-case performance was pinned down by Vašek Chvátal in 1979 (building on earlier work by David Johnson and László Lovász): it always finds a cover of size at most H(n) ≈ ln n + 1 times the true optimum, where n is the number of elements and H(n) is the n-th harmonic number. That’s a solid guarantee, but for decades it was an open question whether some cleverer, more sophisticated algorithm could do meaningfully better in the worst case.

The matching hardness result

In 2014, Irit Dinur and David Steurer proved that approximating set cover to within (1 − o(1))·ln n is NP-hard. That closes the gap almost exactly: greedy’s ln n + 1 upper bound and Dinur–Steurer’s (1−o(1))ln n hardness result pin the true worst-case approximation ratio to essentially ln n, with no room left for a smarter algorithm to meaningfully improve on the decades-old greedy heuristic.

Why that’s a satisfying kind of answer

Most approximation-algorithm stories in the Registry involve an open gap: a known achievable ratio and a weaker proven hardness bound, with room in between for either side to move. Set cover is one of the rarer cases where the gap has actually closed — the simplest possible algorithm turned out to already be optimal, and a matching hardness proof confirms there was never a better one to find.

Why it’s here

The Registry tracks both directions of this problem — what an algorithm can guarantee, and what no algorithm can beat — as a single frontier, exactly the way it tracks open problems in mathematics and physics. Here the frontier happens to be closed.

Primary source

Dinur & Steurer, “Analytical Approach to Parallel Repetition,” STOC (2014) ↗