Greedy Set-Cover Heuristic¶
An approximation method — instantiates Greedy Stepwise Commitment
Repeatedly adds the candidate covering the most still-uncovered need per unit cost — cheap, transparent, and provably within a logarithmic factor of the smallest possible cover.
Greedy Set-Cover Heuristic builds a cover of a universe of needs by repeatedly adding the candidate set that covers the most still-uncovered need per unit cost, subtracting whatever it just covered from the residual, and repeating until nothing is left uncovered. Its distinguishing move is that the score is marginal against the shrinking remainder: a candidate that was the best pick a moment ago may be nearly worthless now because most of what it covers has already been taken. And unlike an ad-hoc coverage grab, it comes with a known worst-case guarantee — the cost of the cover it produces is provably within a logarithmic factor of the smallest cover that could ever exist.
Example¶
A city must place ambulance stations so every one of its 140 neighbourhoods sits within an eight-minute drive of one. Each candidate site covers a different subset of neighbourhoods — some dense but overlapping downtown, some sprawling suburban — at a different build cost. The Greedy Set-Cover Heuristic picks the site covering the most still-uncovered neighbourhoods per dollar first. A suburban site reaching 22 uncovered neighbourhoods leads, even though a downtown site touches more neighbourhoods in total, because most of those already fall within reach of an existing station.
It marks those 22 covered, then re-scores every remaining site against the shrunken residual — the downtown site's marginal value collapses now that its overlap is counted out — and keeps going until all 140 are covered. The cover it lands, ≈nine sites, is not guaranteed minimal, but it is guaranteed to sit within a small logarithmic factor of the fewest sites that could ever suffice — a bound the raw "most coverage first" instinct cannot promise.
How it works¶
- Score by marginal coverage. Rank each candidate by newly-covered need ÷ cost, evaluated against the current uncovered set.
- Take the max and add it to the cover.
- Shrink the residual. Subtract its coverage, then re-score every remaining candidate against the smaller residual.
- Stop when the residual is empty (full cover) or the budget is spent (best partial cover).
What distinguishes it: the re-scoring against the residual after every pick — the score is never static — plus a solution-quality guarantee a coverage heuristic normally lacks.
Tuning parameters¶
- Cost normalisation — cover-per-dollar versus cover-per-item. Determines whether the heuristic minimises spend or count.
- Residual weighting — treat every uncovered element equally, or weight by importance/population so under-served needs pull harder on the score.
- Partial-cover budget — a hard budget that stops the pass early and accepts the best coverage affordable, versus running to full cover.
- Redundancy trim — a cleanup pass that drops a set made redundant by later picks; pure greedy can leave one behind.
- Benchmark cadence — how often to check the greedy cover against a lower bound or an exact solve on small instances.
When it helps, and when it misleads¶
Its strength is that it turns an NP-hard covering problem into a fast, transparent pass, and — unusually for a greedy heuristic — carries a provable ceiling on how far from optimal it can fall, roughly a factor of ln n in the number of needs.[n1] That ceiling is essentially the best any efficient method can promise for this problem, so greedy here is not merely convenient but close to the frontier of what's possible.
The logarithmic factor is still a real gap: on adversarial instances greedy genuinely can spend that multiple over the optimum. The per-cost score is only as honest as the cost model — a cheap-looking set with hidden downstream cost flatters its marginal score — and because it chases raw coverage, without weighting it can leave the least-served needs for last and then miss them under a budget cut. The classic misuse is presenting the greedy cover as the minimum rather than a bounded approximation. The discipline is to keep a benchmark — a lower bound, or an exact solve on a reduced instance — so the actual gap, not the guarantee, is what gets reported.
How it implements the components¶
local_priority_score— the marginal-coverage-per-cost score each candidate is ranked by, recomputed against the residual every round.residual_capacity_tracker— the shrinking set of still-uncovered needs that every score is measured against; the pass ends when it empties.validation_benchmark_set— the lower bound or reduced exact solve that checks how close the greedy cover actually lands to optimal.
It does not commit against an external deadline (Earliest-Deadline-First Dispatch), enforce a structural invariant or matroid guarantee (Kruskal-Style Edge Acceptance), or maintain the settled shortest-path state of a routing search (Dijkstra-Style Frontier Expansion).
Related¶
- Instantiates: Greedy Stepwise Commitment — the approximation case, where the greedy cover carries a provable bound on its own suboptimality.
- Sibling mechanisms: Highest-Marginal-Gain-First Rule · Greedy Assignment Pass · Sorted Candidate Sweep · Trap-Sentinel Escalation
Editorial Notes¶
Form Classification¶
Form family: Analysis, Modeling & Optimization
Rationale: The heuristic repeatedly computes marginal uncovered need per unit cost and derives a near-minimal covering set.
Nearest alternative: Decision, Gate & Allocation — Candidates are selected iteratively, but the operative form is an optimization algorithm rather than case-by-case authority allocation.
Review outcome: Adjudicated after independent review; high confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Cross-disciplinary synthesis
Present-day reach: Universal
Rationale: Approximation algorithms established greedy set cover and its logarithmic performance guarantee.
Related originating lineages:
- Mathematics — Combinatorics supplies the set-cover problem and harmonic approximation bound.
- Operations Research — Covering models materially apply the heuristic to constrained resource selection.
Review resolution: Both reviewers agree that computer_science is primary: Approximation algorithms established greedy set cover and its logarithmic performance guarantee. I retain mathematics, operations_research only as formative lineage, not as a list of later applications. I resolve origin_mode as cross_disciplinary_synthesis because the artifact joins distinct disciplinary contributions. I resolve domain_reach as universal because it is broadly applicable across essentially all domains. Encyclopedia synthesis is false because the exact generalized packaging is already established enough that encyclopedia-specific synthesis is not required.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
This is the canonical case where greedy is not a compromise but nearly the best available: no polynomial method can guarantee better than a logarithmic factor unless P = NP. So the interesting question is rarely "should we use greedy?" but "how tightly can we bound the gap on this instance?" — which is why the benchmark, not the headline cover, is the deliverable that matters.
[n1] The greedy set-cover heuristic achieves an approximation ratio of H(n) = 1 + ½ + … + 1/n ≈ ln n, where n is the size of the largest set (Johnson; Lovász; Chvátal). For the general problem this is essentially optimal — no polynomial-time algorithm can do asymptotically better unless P = NP. ↩