The Harmonic Bound for Greedy Set Cover

Set cover is the canonical problem where greedy is the right answer and cannot be the optimal one. Given a universe of $n$ elements and a family of subsets with costs, choose the cheapest subfamily whose union is the universe. The greedy rule, repeatedly take the set with the lowest cost per newly covered element, runs in polynomial time and guarantees a solution within a factor of $H(n) = 1 + 1/2 + \dots + 1/n$ of optimal. That factor grows without bound, so no constant improvement is available from this algorithm, and the harmonic bound matches the best hardness result known for the problem.

Why the obvious objective fails

The natural greedy instinct, take the largest set first, has no ratio guarantee at all. Consider a universe of $n$ elements, one set $A$ covering all $n$ of them at cost $n$, and $n$ sets each covering one element at cost 1. Largest-first takes $A$ for total cost $n$, while the optimum takes the singletons for cost $n$, so the ratio is 1 on this instance. Modify it: $A$ costs $n^2$ and the singletons cost 1 each. Largest-first still takes $A$ and pays $n^2$ against an optimum of $n$, a ratio of $n$. The set sizes carry no information about cost.

Cost-per-element fixes this by making the two quantities comparable. The rule is to select, at each step, the set minimizing $c(S)/|S \setminus C|$ where $C$ is the set of elements already covered and $c(S)$ is the set’s cost. The denominator is the count of new elements, not total size, which is what makes the analysis work: a set that overlaps heavily with what is already covered is expensive per unit of progress even if its total size is large.

def greedy_set_cover(universe, sets, cost):
    # sets: list of frozensets; cost: list of positive numbers
    uncovered = set(universe)
    chosen = []
    total = 0.0
    while uncovered:
        best_i, best_ratio = -1, float('inf')
        for i, s in enumerate(sets):
            gain = len(s & uncovered)
            if gain == 0:
                continue
            ratio = cost[i] / gain
            if ratio < best_ratio:
                best_i, best_ratio = i, ratio
        if best_i < 0:
            return None  # some element is in no set
        chosen.append(best_i)
        total += cost[best_i]
        uncovered -= sets[best_i]
    return chosen, total

The inner scan costs $O(n)$ per set considered, so one round over all $m$ sets is $O(nm)$ and a full run of up to $n$ rounds is $O(n^2 m)$ in the straightforward form. Maintaining a counter of uncovered elements per set and updating only the sets containing the newly covered element brings typical inputs down substantially, but the bound for the naive version is the one stated.

The charging argument

The ratio bound is proved by charging each element’s coverage to the sets in an optimal solution, and the harmonic series appears because the charges are assigned in order of coverage.

Let $C^*$ be an optimal cover with total cost $\mathrm{OPT}$. Fix an ordering of the elements $e_1, \dots, e_n$ in the order greedy covers them, and let $c_i$ be the cost per element of the set that covers $e_i$ at the moment it is chosen. Then the total cost of the greedy solution is $\sum_i c_i$.

For each element $e_i$, charge $c_i$ to a set $S^* \in C^$ that contains $e_i$. Each set $S^$ receives charges from the elements it covers, and the total charged to $S^$ is what must be bounded by $c(S^) \cdot H(|S^*|)$.

Consider a fixed $S^$ and let its elements be covered by greedy at positions $i_1 < i_2 < \dots < i_k$, where $k = |S^|$. When greedy covers the $j$-th of these, at least $k - j + 1$ elements of $S^$ are still uncovered, since $j - 1$ of them were covered earlier and $k - j + 1$ remain. Greedy chose a set with cost per new element $c_{i_j}$, and $S^$ was available as a candidate with cost per new element at most $c(S^*)/(k - j + 1)$. By the choice of minimum ratio,

$$ c_{i_j} \le \frac{c(S^*)}{k - j + 1} $$

Summing over $j = 1 \dots k$ gives

$$ \sum_{j=1}^{k} c_{i_j} \le c(S^) \sum_{j=1}^{k} \frac{1}{j} = c(S^), H(k) \le c(S^*), H(n) $$

Summing over all sets in $C^$ gives total greedy cost at most $H(n) \sum_{S^ \in C^} c(S^) = H(n),\mathrm{OPT}$.

The argument’s key step is the availability of $S^*$ as a candidate. Greedy minimizes over all sets with nonzero gain, so any particular set’s ratio is an upper bound on the minimum. The bound therefore holds for any tie-breaking rule, and it holds whether or not the covering sets that greedy never selects happen to be cheap.

$H(n)$ is between $\ln n$ and $\ln n + 1$; for $n = 1000$ it is about 7.49, and for $n = 10^6$ about 14.39. The bound is therefore logarithmic and grows slowly with the size of the universe, which is why a logarithmic guarantee is workable where no exact algorithm finishes on the instances at hand.

Tightness and the hardness ceiling

The bound is asymptotically tight, and the reason is not a clever instance but a limitation on what any polynomial-time algorithm can do. Feige’s result shows that set cover cannot be approximated within a factor of $(1 - o(1))\ln n$ in polynomial time unless NP has quasi-polynomial-time algorithms. The greedy bound and that hardness bound agree in order: both are $\Theta(\ln n)$. Set cover is one of the few problems where the algorithm and the lower bound meet, so no polynomial-time improvement on the ratio is available without an unexpected complexity-theoretic collapse.

What an instance that defeats greedy looks like structurally: the optimum uses a small number of large sets, and greedy’s first pick is a set that is large but overlaps those optimum sets heavily. After the first pick, each remaining optimum set covers only a small amount of new ground, so greedy’s ratio test prefers sets that cover a few fresh elements cheaply, and it ends up taking many small sets instead of the few large ones. Each such choice is locally optimal by the ratio test and globally costly. The construction that achieves the harmonic factor has $n$ elements and forces greedy to take one set per “layer”, each covering a smaller fraction of what remains than the previous one, while a constant number of sets covers the whole universe.

The lesson is that the ratio bound is a worst case, not a prediction: it states what no instance can do worse than, not what a given instance will cost. The structure that makes an instance adversarial is overlap between the sets greedy takes and the sets the optimum takes; where no such overlap exists, the ratio test and the optimum point in the same direction.

The frequency parameter

Many instances have a bounded frequency: each element belongs to at most $f$ sets. The charging argument above bounds the charge on each optimal set $S^$ by $c(S^) H(|S^*|)$, so the ratio is $H(\Delta)$ for $\Delta$ the size of the largest set in the instance. That is never worse than $H(n)$, and it is constant whenever no individual set is large.

Bounded frequency gives a different route to a constant, and it does not go through the charging argument at all.

There is a stronger and simpler algorithm for the frequency-bounded case: solve the LP relaxation, round up every set whose fractional value is at least $1/f$, and observe that every element is then covered, since at most $f$ sets contain it and their fractional values sum to at least 1, so the largest of those $f$ values is at least $1/f$. The cost of the rounded solution is at most $f$ times the LP value, hence at most $f \cdot \mathrm{OPT}$.

The two guarantees are incomparable. $H(\Delta)$ is logarithmic in the size of the largest set and says nothing about frequency; $f$ is linear in the frequency and says nothing about size. An instance whose sets are small but heavily shared is handled better by the harmonic bound, and one with few sets per element but large sets is handled better by rounding.

What greedy set cover is actually used for

The algorithm’s practical role is as a workhorse where the ratio bound is a safety net rather than a description of typical behaviour. Three properties make it attractive.

Monotonicity. Adding more sets to the instance cannot increase the greedy solution’s cost, and adding an element to the universe cannot decrease it. These are not true of every heuristic, and they make the algorithm safe to run on incrementally updated instances.

Monotone progress. Every round covers at least one element that was previously uncovered, so at any point the chosen sets form a cover of the part of the universe reached so far, and their cost is an upper bound on the cost of the cover that will be produced. A caller working to a budget can stop when the accumulated cost passes a threshold and keep the partial solution. The knapsack value-scaling algorithm has no such property: its precision is a parameter fixed before the computation starts, and the table it fills is sized by that parameter rather than by the instance.

Lazy evaluation. The cost per new element of a set only increases as elements get covered, so the key stored for a set in a priority queue is always a lower bound on its current ratio. A queue that pops the set with the smallest stored key, recomputes that set’s true ratio, and reinserts it with the recomputed key if it is larger, therefore recomputes a ratio only for the sets that reach the top of the queue. This is the standard optimization for large instances, and it yields the same cover as the naive scan.

The LP relaxation of set cover has an integrality gap of $\Theta(\log n)$, not a constant: there are instances on which the fractional optimum is 1 while every integral cover costs $\Omega(\log n)$. Rounding a fractional solution therefore cannot produce a constant factor without using something beyond the LP value, and the natural threshold rule yields only the frequency-bounded $f$ of the previous section. The way out is not to round a primal solution at all but to construct a dual solution alongside it, which is the primal-dual schema and which yields the same $H(n)$ guarantee by a different route with different constants.

Related covering variants

The same greedy rule with a modified ratio applies to several relatives. In weighted set multicover, each element must be covered a specified number of times, and the ratio test is taken against the remaining demand rather than a binary covered/uncovered state; the analysis follows the same charging shape with the demands in place of the set sizes. In the partial cover problem, where covering a required fraction of the universe suffices, the greedy rule stops when the fraction is reached and the bound degrades gracefully. In the maximum coverage problem, where the budget is a number of sets and the objective is the count of covered elements, greedy gives a $(1 - 1/e)$ approximation, and the constant comes from a completely different argument based on submodularity rather than from the harmonic series. The distinction matters: the two problems look like duals, and their guarantees have different shapes because one is a minimization with a covering constraint and the other is a maximization with a cardinality constraint.