Overview
Greedy set cover maintains uncovered elements and adds the set with the best coverage gain, often measured as new elements covered per unit cost.
CoreSource checked
Greedy Set Cover
Approximates set cover by repeatedly choosing the set that covers the most uncovered elements per cost.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Optimization
- Difficulty
- Intermediate
- Family
- Approximation Algorithms
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 8
- Code example
- Ready
- Visualization
- Ready
Core Concepts
set cover approximationapproximation algorithmsgreedy choiceoptimization
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n log n)
Worst
O(n^2)
Space
O(n)
When to Use
- Use when an approximate cover is acceptable and exact search is too expensive.
- Use when sets and uncovered elements can be updated efficiently.
When Not to Use
- Avoid when exact minimum cover is required for a small instance that can be solved exactly.
- Avoid when set costs or coverage data are unreliable.
What It Does
- Greedy Set Cover uses repeatedly selecting the set that covers the most uncovered elements per cost for set cover approximation
- Organizes the work around set cover approximation and approximation algorithms.
Use Cases
- Production and research workloads requiring approximation algorithms via Approximates set cover by repeatedly choosing the set that covers the most uncovered elements per cost.
- Approximation Algorithms pipelines where O(n log n) time and O(n) space fit system constraints.
- Engineering comparisons against Algorithm X and Dancing Links when tuning approximation algorithms.
Inputs
- Objective, constraints, and candidate variables
- Problem-specific costs or feasibility rules
Outputs
- Best known feasible solution
- Optimality or approximation result when available
Key Formulas (1)
Greedy score
score(S) = newlycovered(S) / cost(S)
score(S) = newly_covered(S) / cost(S)Selects the set with the best uncovered elements per unit cost.
Pseudocode
- 1.Set uncovered to the full universe
- 2.While uncovered is not empty
- 3.Choose the set with best uncovered gain per cost
- 4.Add it to the cover
- 5.Remove its elements from uncovered
- 6.Return the chosen sets
Canonical Example
- Input
- universe {1,2,3,4}, sets A={1,2}, B={2,3,4}, C={4}
- Output
- choose B, then A to cover all elements
- Explanation
- B covers three uncovered elements first; A then covers the remaining element 1.
Implementation Notes
- Track uncovered elements explicitly.
- Score each candidate by newly covered elements, or by cost per newly covered element.
- Test cases where the greedy first choice is not globally optimal.
Common Pitfalls
- Counting already-covered elements inflates a set's apparent value.
- Tie-breaking can change the chosen cover size.
- Greedy choices do not generally produce an optimal cover.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow repeatedly selecting the set that covers the most uncovered elements per cost on a small set cover approximation example.
Step 1 of 6: Set uncovered to the full universe
optimization-mechanismNotes
The greedy set-cover bound is approximate; it is still often useful because the implementation is simple and scalable.
Sources (2)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Greedy Set Cover's standard algorithm design, invariants, and complexity analysis.
Open sourceThe Design of Approximation Algorithms
BookApproximation algorithms reference for Greedy Set Cover's guarantee, reduction, or approximation-analysis model.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
ApproximatesAlgorithm X
Optimization · Core
Greedy Set Cover gives an approximate or heuristic answer for the problem family associated with Algorithm X.
Compare with thisApproximatesDancing Links
Optimization · Core
Greedy Set Cover gives an approximate or heuristic answer for the problem family associated with Dancing Links.
Compare with thisApproximatesBranch-and-Bound Set Packing
Optimization · Extended
Greedy Set Cover gives an approximate or heuristic answer for the problem family associated with Branch-and-Bound Set Packing.
Compare with thisRelationships
View full relationship pageApproximatesAlgorithm X
Greedy Set Cover gives an approximate or heuristic answer for the problem family associated with Algorithm X.
ApproximatesDancing Links
Greedy Set Cover gives an approximate or heuristic answer for the problem family associated with Dancing Links.
ApproximatesBranch-and-Bound Set Packing
Greedy Set Cover gives an approximate or heuristic answer for the problem family associated with Branch-and-Bound Set Packing.
Related Algorithms
Tags
OptimizationApproximation