Set Cover Greedy, in depth: the H(n) pricing proof, a tight instance, weighted and lazy greedy, and the variants you will meet

The greedy algorithm

Unweighted greedy keeps a set U of uncovered elements. It repeatedly takes the set that covers the most of U, removes those elements, and stops when U is empty. The weighted version takes the set with the lowest price, defined as cost divided by the number of newly covered elements. Unweighted greedy is the special case where every cost is 1.

def greedy_set_cover(universe, sets, cost=None):
    """sets: dict name -> set of elements; cost: dict name -> positive number."""
    cost = cost or {name: 1.0 for name in sets}
    uncovered = set(universe)
    if not uncovered <= set().union(*sets.values()):
        raise ValueError("some elements are in no set: no cover exists")
    chosen, price = [], {}
    while uncovered:
        best, best_ratio = None, float("inf")
        for name, s in sets.items():
            gain = len(s & uncovered)
            if gain and cost[name] / gain < best_ratio:
                best, best_ratio = name, cost[name] / gain
        for e in sets[best] & uncovered:
            price[e] = best_ratio          # what each element "paid"
        uncovered -= sets[best]
        chosen.append(best)
    return chosen, price

The feasibility check matters. If any element appears in no set, the loop never terminates in a naive version, or fails with a confusing error. The price map is not needed for the answer. It is the certificate the proof uses, and it is useful in logs: elements that paid a high price are the expensive ones to cover.

Mapping a real problem onto this interface is usually the hard part. For test selection, the universe is the set of changed lines or branches. Each test is a set holding the lines it executes, taken from a coverage run, and its cost is its run time. Greedy then picks tests by seconds per newly covered line. The same template works for features and fraud cases, or for cache nodes and regions. Decide what an element is, what a set is and what a set costs, and keep the mapping code separate from the algorithm so both can be tested.

A worked run

Take the universe {1, ..., 10} and five unit-cost sets: A = {1,2,3,4,5,6}, B = {1,2,3,7}, C = {4,5,8,9}, D = {6,7,10}, E = {8,9,10}.

Greedy returns {A, E, B}, which has cost 3. Is that optimal? No pair of sets covers all ten elements. A pair containing A would need one set holding all of {7, 8, 9, 10}, and none does. Without A, two sets of at most four elements cover at most 8. So 3 is optimal here. The prices sum to 6 x 1/6 + 3 x 1/3 + 1 x 1 = 3, and that sum always equals the cost of the greedy cover. Note the tie at step 3. Real implementations need a deterministic tie-break, for example lowest cost first and then a stable id, or reruns produce different covers and confuse anyone diffing them.

Why greedy is within H(n): the pricing proof

Let OPT be the cost of an optimal cover. Number the elements e₁, ..., e_n in the order greedy covers them, breaking ties within a step arbitrarily. Just before e_k is covered, at least n - k + 1 elements are uncovered. The optimal cover covers all of them with total cost OPT, so at least one of its sets covers them at price at most OPT / (n - k + 1). Greedy picks the cheapest price available, so the price charged to e_k is at most OPT / (n - k + 1). Summing over all elements gives:

greedy cost = sum of prices
            <= OPT * (1/n + 1/(n-1) + ... + 1/1)
             = OPT * H(n),   where H(n) <= ln n + 1

A sharper version charges each set S in the optimal cover separately. The elements of S, as greedy covers them, pay at most cost(S) times H(|S|). That gives the bound H(d), where d is the size of the largest set. When sets are small, this is far better than ln n. If no set has more than 5 elements, greedy is within H(5), about 2.28, of optimal however large the universe is.

This proof style is worth learning. It assigns each element a price, bounds every price by comparing it with what the optimum must pay at that moment, and sums. The same argument is the dual-fitting view of the LP dual. Scaled by 1/H(d), the prices form a feasible dual solution, which is why greedy's result also bounds the LP optimum.

When greedy is that bad, and why nobody does better

The logarithm is not just a weak proof. Take two rows R1 and R2 and k column groups C1, ..., Ck, where group Ci has 2ⁱ elements split evenly between the rows. Each row then holds 2^k - 1 elements and n = 2^k+1 - 2.

At the start, Ck covers 2^k elements and each row covers 2^k - 1, so greedy takes Ck. Afterwards the rows have 2^k-1 - 1 uncovered elements each and C(k-1) has 2^k-1, so the pattern repeats. Greedy takes all k columns where 2 sets would do, a ratio of k/2, which is about (log₂ n)/2. Run the code above on this instance to see it happen. That makes a good unit test, because a broken implementation often does better on this instance than a correct one.

Hardness says the logarithm cannot be escaped in general. Feige (1998) showed that no polynomial algorithm achieves (1 - epsilon) ln n unless NP has quasi-polynomial-time algorithms. Dinur and Steurer (2014) proved the same threshold assuming only P != NP. Greedy is essentially optimal among efficient algorithms in the worst case, and it often does much better on real data.

Scaling up: lazy greedy with bitsets

The simple loop costs O(m x n) per step for m sets. With millions of sets that is too slow. Two observations fix it. First, a set's gain can only shrink as elements get covered. The coverage function is submodular. So a gain computed earlier is an upper bound on the gain now. Keep sets in a heap keyed by their stale price. Pop the best, recompute its true price, and if it still beats the next stale entry it is the true best, so take it. Otherwise push it back with the fresh price. Second, store sets as integer bitsets so that intersection and popcount are word operations.

import heapq

def lazy_greedy(n, sets, cost):
    """sets: list of int bitmasks over n elements; cost: list of floats."""
    full = (1 << n) - 1
    covered = 0
    heap = [(cost[i] / bin(s).count("1"), i) for i, s in enumerate(sets) if s]
    heapq.heapify(heap)
    chosen = []
    while covered != full:
        if not heap:
            raise ValueError("universe not coverable")
        _, i = heapq.heappop(heap)
        gain = bin(sets[i] & ~covered).count("1")
        if gain == 0:
            continue                                  # fully redundant now
        fresh = cost[i] / gain
        if heap and fresh > heap[0][0]:
            heapq.heappush(heap, (fresh, i))          # stale: re-queue
            continue
        chosen.append(i)
        covered |= sets[i]
    return chosen

In practice most pops are accepted on the first recheck, so the run time is dominated by the initial heap build plus a small multiple of the cover size. For a universe too big for one integer, use a bitmap library such as Roaring bitmaps, or store each set as a sorted element list and keep a covered-flag array.

Variants

Several variants are close enough that people reach for the same code:

• Maximum coverage. You may pick only k sets and want to cover as many elements as possible. Run greedy for k steps. Nemhauser, Wolsey and Fisher (1978) showed this covers at least (1 - 1/e), about 63%, of the best possible coverage. This is the usual model for sensor placement and influence selection.
• Partial cover. Cover at least a fraction p of the universe. Stop greedy once the target is met. The logarithmic guarantee carries over to the shortened run.
• Low-frequency instances. If every element lies in at most f sets, LP rounding, where you take every set whose fractional value is at least 1/f, gives an f-approximation. That beats ln n when f is small. Vertex cover is the case f = 2. See LP rounding and vertex cover approximation.
• Exact solutions for moderate sizes. An integer program solver with greedy as a warm start often proves optimality for thousands of sets. Use it when the cover is bought once and is expensive.

Failure modes

What goes wrong in production:

• Uncoverable elements. An element no set contains makes the loop spin or crash. Check that the union of all sets is the universe before the loop, and report the orphans.
• Zero or negative costs. A zero-cost set has price 0 and is always picked first. That is fine if intended. Negative costs break the analysis. Validate inputs.
• Nondeterministic ties. Python set iteration and dict order across runs can change which tied set wins. Sort by (price, cost, id).
• Redundant sets in the output. Greedy can pick a set whose elements were later all covered by subsequent picks. A cheap post-pass helps: scan chosen sets from most to least expensive and drop any whose elements are all covered by the others.
• Trusting the bound as the result. H(d) is a worst case. To know how good a specific cover is, compute a lower bound. The LP relaxation, or the price sum divided by H(d), tells you how far from optimal you can be.

What to do next

1. Write your problem as universe, sets and costs, and check that the union covers everything.
2. Run the simple greedy on a sample, logging prices to see which elements are expensive.
3. Add the two-row tight instance and the ten-element example as unit tests with known answers.
4. Switch to lazy greedy with bitsets once m x n per step becomes slow, and confirm identical output on the tests.
5. Add the redundancy-removal post-pass and a deterministic tie-break.
6. Compute an LP lower bound on one real instance to learn how close to optimal greedy really is.
7. Read approximation algorithms and greedy algorithms to place set cover among its relatives.