Greedy Set Cover Certificate

Compare greedy covering decisions with an exact small optimum and a provable approximation certificate.

Experiment

Open the Greedy Set Cover Certificate module to explore the limits of the greedy algorithm.

1. Set Set family to Greedy trap, Universe size to 6, and Costs to Unit.
2. Observe that the greedy algorithm selects A, B, and C with a cost of 3, while the optimal cost is 2.
3. Change Costs to Expensive A. This assigns a cost of 3 to set A and 1 to others.
4. Observe that the greedy algorithm now avoids A initially and selects B and C with a cost of 2, matching the optimal cost.
5. Change Set family to Uncoverable.
6. Observe that the status becomes Uncoverable with 1 uncovered element, and the optimal cost and ratio are Unavailable.