Greedy Set Cover Certificate

Worked Example

Consider the Greedy trap family with a Universe size of 6 and Unit costs.

The universe is {0, 1, 2, 3, 4, 5}. The sets are:

• A: {0, 1, 2, 3} (cost: 1)
• B: {0, 1, 4} (cost: 1)
• C: {2, 3, 5} (cost: 1)
• D: {4} (cost: 1)
• E: {5} (cost: 1)

The greedy algorithm picks the set with the highest number of newly covered elements per unit cost.

1. Initially, A covers 4 elements, B covers 3, C covers 3. A is selected. Total cost: 1. Uncovered: {4, 5}.
2. Now, B covers 1 element (4), C covers 1 element (5), D covers 1 (4), E covers 1 (5). All have ratio 1/1=1. Breaking ties alphabetically, B is selected. Total cost: 2. Uncovered: {5}.
3. Now, C covers 1 (5) and E covers 1 (5). C is selected alphabetically. Total cost: 3. Uncovered: none.

The greedy cost is 3. However, the optimal cover is just sets B and C, which together cover all 6 elements at a cost of 2. Thus, the greedy algorithm is suboptimal. We also compute a certificate bound: the harmonic bound H_d * optimalCost, where d is the maximum size of any chosen set (here, d=4). H₄ = 1 + 1/2 + 1/3 + 1/4 = 25/12 = 2.0833. The bound is 2.0833 * 2 = 4.166... We verify that the greedy cost (3) is indeed ≤ 4.166.

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.

Limitations

This module uses a small universe size (up to 6 elements) to allow enumerating all 2⁵ = 32 subset combinations to find the exact optimum. For larger instances, computing the optimal set cover is NP-hard and exact enumeration would be prohibitively slow in the browser. Floating point arithmetic is subject to small precision limitations, so an absolute tolerance is used for numerical comparisons in automated checks.

References

The harmonic bound H_d for the greedy set cover approximation and the construction of "greedy trap" instances are standard results in approximation algorithms.

See CS 473 Lecture 11: Approximation Algorithms II from UIUC for a detailed proof of the approximation ratio.