Set Cover (Greedy Approximation)

Set Cover is a classic NP-hard problem with a beautiful, simple greedy that gets you close to optimal. It teaches the core greedy move: at every step, take the choice that helps the most right now.

The slow way first

The exact answer requires trying every combination of subsets and keeping the smallest cover — that is exponential (2^m subsets to consider). Even for a handful of sets that explodes fast, and the problem is provably NP-hard, so no known polynomial algorithm finds the true minimum.

The question to ask: if I cannot afford the optimum, what cheap rule gets me close? The answer is to be greedy about coverage.

The idea: always grab the most new coverage

Keep a covered set, starting empty. Repeat: pick the subset that adds the most still-uncovered elements, add it to the answer, and mark its elements covered. Stop when everything is covered.

The key insight: we score by new coverage, len(s - covered), not raw size. A big subset that overlaps what we already have is worth little. This greedy is guaranteed to use at most ln(n) times the optimal number of sets — a strong approximation.

Walk through it

Step through the animation. Round 1: S1 adds 4 new elements (most), so we pick it and 4 turn covered. Round 2: only 6 remain — S2 would add just 1, but S3 adds 2, so S3 wins. Now everything is covered and we return [S1, S3].

Pseudocode

covered = empty set
chosen = empty list
while covered does not equal the universe:
    best = the subset maximizing len(subset - covered)   # most new elements
    if best adds nothing new:
        break                                            # cannot make progress
    add best to chosen
    covered = covered union best
return chosen

The Python solution

def set_cover(universe, subsets):
    covered = set()
    chosen = []
    while covered != universe:
        best = max(subsets,
                   key=lambda s: len(s - covered))
        if not (best - covered):
            break
        chosen.append(best)
        covered |= best
    return chosen

• covered tracks every element we have already covered; chosen is the answer we are building.
• The loop runs until covered equals the full universe.
• Lines 5 and 6 are the greedy choice: max(... key=lambda s: len(s - covered)) picks the subset with the most elements not yet in covered.
• if not (best - covered) guards against an impossible cover — if even the best subset adds nothing, we stop.
• covered |= best is set union: we fold the chosen subset into covered.

Complexity

With m subsets and universe size n, each round scans every subset (re-scoring against covered), and there are at most m rounds, so the greedy is polynomial. It returns a cover at most ln(n) times the optimal — the best ratio any polynomial algorithm can guarantee unless P = NP.

When this pattern shows up

Practice