Given a universe of elements and a family of sets, each covering some subset of the universe, pick the fewest sets whose union is the whole universe. Every element has to end up covered by at least one chosen set; picking a set costs 1, regardless of how much or little new ground it covers. This is Set Cover — one of the classic NP-hard problems, meaning no known algorithm finds the true minimum cover in better than exponential time in the worst case. The greedy rule here doesn't try to solve it exactly: repeatedly pick whichever remaining set covers the most still-uncovered elements, until nothing is left. That single rule is provably never worse than a specific, known factor off the true optimum, no matter the input — a guarantee, not a hope.
This is the site's sixth entry filed under Greedy, after Huffman Coding, Activity Selection, Fractional Knapsack, Coin Change, and Job Sequencing with Deadlines — and the first of the six that is never claimed to be exactly optimal. Coin Change's greedy rule is exact for canonical denominations and can fail arbitrarily badly on others, with no guaranteed closeness to the true answer either way; every other entry in the category is provably exact, full stop. Set Cover's greedy rule sits in a third position: it essentially never lands on the true optimum for a nontrivial instance, but it comes with a proven ceiling on exactly how far off it can be — the site's first genuine approximation algorithm in the strict sense, rather than a correct-or-heuristic rule.
Type a universe of candidate sets as name:elem-elem-elem triples (comma-separated,
elements hyphen-separated), pick a selection strategy, and press Load, then
Step or Run. The numbered grid is the universe — a cell turns solid
green the moment some chosen set covers it. The chips below are the candidate sets; a chip turns
green once it's picked, faded-dashed if a pass skips it for contributing nothing new. The demo also
brute-forces the true minimum cover for comparison (every subset of sets, capped at 12 sets so it
stays instant), so a strategy that uses more sets than necessary is visible immediately, not just
claimed.
universe
candidate sets
The greedy rule doesn't need to know anything about the optimal solution to earn its guarantee — the proof works by comparing every round's progress against the optimal cover's size alone, never its actual contents.
Claim — every greedy round covers at least a 1/OPT fraction of what's still
uncovered. Let OPT be the size of a true minimum cover, and say R
elements remain uncovered at the start of some round. The optimal cover's sets, restricted to just
those R elements, still cover all of them — the optimal cover covers the whole universe,
so it certainly covers whatever's left of it. That means R elements are split across at
most OPT sets, so by pigeonhole at least one of those sets covers at least
R / OPT of them. Greedy doesn't have to find that particular set — it just picks
whichever available set has the single best marginal gain, and since the pigeonhole set is available
too, greedy's actual pick is guaranteed to cover at least R / OPT new elements as well.
That single guarantee is enough to bound the whole run. If R elements
remain before a round, at most R(1 - 1/OPT) remain after it. Starting from
n elements (the universe size) and shrinking by that factor every round, fewer than 1
element remains — i.e. none — after roughly OPT · ln(n) rounds. So greedy always
finishes in O(OPT · ln n) sets. (The textbook-tight version of this argument, using
a slightly different accounting per element rather than this round-by-round geometric shrink, proves
the sharper bound H(n) = 1 + 1/2 + … + 1/n ≈ ln(n) + 1 — the two agree
asymptotically; the shrinking argument above is the easier one to see by hand.) Nowhere in either
argument does the tie-break rule for equal-gain sets matter — any max-gain choice satisfies the
pigeonhole bound, so ties can be broken arbitrarily (this demo breaks them by input order, purely for
reproducibility) without weakening the guarantee.
On the default data — universe of 10 elements, true optimum 2 sets (P1+P2,
verified below) — the bound says greedy can never need more than
⌊2 × H(10)⌋ = ⌊2 × 2.929⌋ = 5 sets. The demo's
actual greedy run uses 3 — comfortably under the guarantee, which is normal: H(n) is a
worst-case ceiling, not a typical-case prediction, and most real instances land well inside it.
function greedySetCover(universe, sets) {
// sets: [{ name, elements: Set<number> }], in a fixed input order
const covered = new Set();
const cover = [];
let remaining = sets.slice();
while (covered.size < universe.length) {
let best = null, bestGain = -1;
for (const s of remaining) {
const gain = [...s.elements].filter(e => !covered.has(e)).length;
if (gain > bestGain) { bestGain = gain; best = s; } // first-seen wins ties
}
if (bestGain <= 0) break; // universe not fully coverable by the given sets
cover.push(best.name);
for (const e of best.elements) covered.add(e);
remaining = remaining.filter(s => s !== best);
}
return cover;
}Greedy is bounded, not exact — even on a small, hand-built instance. The default
data is constructed so that the optimum is exactly 2 sets: P1 = {1,2,3,8,9}
and P2 = {4,5,6,7,10} partition the universe cleanly, confirmed by the
demo's own brute-force check over all 31 non-empty subsets of the 5 candidate sets — no other pair,
and no single set, covers all 10 elements. But T = {1,2,3,4,5,6,7} covers 7
elements on round one — more than either of P1 or P2 alone (5
each) — so greedy takes it first, purely because it's locally the biggest gain available. That single
choice makes the remaining 3 elements ({8,9,10}) impossible to finish in one more set:
P1 now only contributes {8,9} (2 new) since 1, 2, 3 are already covered by
T, and no other set covers all of {8,9,10} either. Greedy needs two more
rounds — P1, tied at gain 2 with D1 and D2 but picked first by
input order, then P2 for the last remaining element — for a total of 3 sets
(T, P1, P2) against a true optimum of 2. Load the default data
and watch both numbers appear side by side in the stats line: this isn't a bug, it's the guarantee
working exactly as advertised — 3 is within the proven ceiling of 5, just not equal to the optimum
of 2.
A different-looking but equally plausible heuristic does worse than greedy, on the exact
same data. Switch the strategy to smallest set first: instead of recomputing the
best remaining gain every round, this rule fixes one pass through the sets sorted by their own
absolute size, smallest first (D1, D2, P1, P2,
T, all size 2, 2, 5, 5, 7), and takes each one that still contributes at least one new
element. It sounds efficient — small sets look "cheap" — but it ignores overlap entirely: it takes
D1 (covers {8,9}), then D2 (only {10} new, since 9
is already covered), then P1 ({1,2,3} new), then P2
({4,5,6,7} new) — 4 sets total, one worse than greedy's 3 and two worse than the true
optimum of 2, and it never even needs to consider T. Smaller sets aren't inherently more
efficient; a set's marginal contribution against what's already covered is the only thing
that matters, and that can only be known by comparing against the current coverage state, not a
set's size in isolation.
The tie-break rule genuinely changes which sets end up in the cover, but never the proven
bound on how many. Round two of the default greedy run has a real three-way tie at gain 2
between P1, D1, and D2 — this demo always resolves ties by
input order, so reordering the input string (e.g. putting D1 before P1)
changes which specific set gets picked at that tie, and can change the final cover's contents.
It does not change the final cover's size here (still 3), and per Why it works above, no
tie-break rule can ever push the total past the H(n) ceiling — only the identity of which
sets get chosen is tie-break-dependent, never the guarantee itself.
Time: greedy runs at most m rounds (one per set eventually chosen, and
never more rounds than there are sets), and each round rescans up to m remaining sets,
computing one set's marginal gain in time proportional to its own size — O(m²n)
worst case, where n is the universe size and every set is close to universe-sized.
Space: O(n + m) for the covered-elements tracker and the remaining-sets
list.
The demo's brute-force optimal-cover check, shown purely for comparison, tries all
2m - 1 non-empty subsets of the m candidate sets and unions each
one against the universe — O(2m · m · n) — capped at 12 sets for
exactly that reason; nothing about the greedy algorithm needs it, and unlike greedy's polynomial
guarantee, finding the true optimum is exactly the NP-hard part this page's algorithm is
approximating around.
See Choosing a Greedy Strategy for how
this entry compares against the site's other nine Greedy entries — short version: this is the
category's one Tier 3 entry, never exactly optimal but provably within a proven
O(ln n) factor of it on every input, a different kind of guarantee than "exact when
the input cooperates."