Min Set Cover

Overview

The minimum set cover problem is concerned with finding the smallest set of sets in a collection such that the union of the sets covers all elements in a particular superset. This is an optimization problem and is known to be NP-hard, but we can still find approximate solutions to it.

The basic idea behind the approximation algorithm is remarkably simple: at each step, choose the set that covers the largest number of elements that have not yet been covered. This greedy strategy does not always find the optimal solution, but it does give us a solution with a logarithmic approximation guarantee.

An Observation

Let the universe of elements we want to cover be $U$, and let $\mathcal{S}$ be a collection of subsets of $U$. We want to find a subcollection $\mathcal{C}\subseteq\mathcal{S}$ such that

$$\bigcup_{S\in\mathcal{C}}S=U.$$

Among all such collections, the optimal solution is the one with the smallest number of sets.

The difficulty is that choosing a set that looks best locally is not necessarily the same as choosing a set that belongs to the globally optimal solution. Nevertheless, we can repeatedly choose the set that covers the most currently uncovered elements and still guarantee that the resulting solution is not too much larger than the optimum.

The Algorithm

Roughly,

def greedy_set_cover(U, S):
    covered = set()
    solution = []

    while covered != U:
        # Choose the set covering the most
        # currently uncovered elements
        best = max(
            S,
            key=lambda X: len(X - covered)
        )

        solution.append(best)
        covered.update(best)

    return solution
  

At every iteration, the algorithm chooses the set that provides the greatest immediate benefit. Once a set has been selected, its newly covered elements are removed from consideration, and the process continues until every element of $U$ has been covered.

Why Does It Work?

Suppose the optimal solution contains $k$ sets. Consider a point during the greedy algorithm when there are $r$ elements left uncovered. Since the optimal solution can cover all of these elements using only $k$ sets, at least one of those sets must cover at least $r/k$ of the remaining elements.

The greedy algorithm chooses the set covering the most remaining elements, so it must cover at least as many as that set. Thus, after one greedy step, the number of uncovered elements decreases by a factor related to

$$1-\frac{1}{k}.$$

Repeatedly applying this observation gives an exponential decrease in the number of uncovered elements. This is the same phenomenon underlying the harmonic-series approximation bound for set cover.

More precisely, the greedy algorithm produces a solution whose size is at most

$$H_n\cdot OPT,$$

where $n=|U|$, $OPT$ is the size of the optimal set cover, and $H_n$ is the $n$th harmonic number:

$$H_n=1+\frac12+\frac13+\cdots+\frac1n.$$

Since $H_n\leq 1+\ln n$, the approximation ratio is $O(\log n)$.

A Useful Lesson

The minimum set cover problem is a nice example of how an optimization problem can remain useful even when finding the exact optimum is computationally difficult. Instead of searching through every possible collection of sets, the greedy algorithm repeatedly makes the locally best choice.

That choice is not guaranteed to be optimal, but the approximation analysis tells us exactly how far from optimal the result can be. This distinction between finding an exact solution and finding a provably good approximation is one of the most useful ideas in the study of NP-hard problems.