# Set Cover / greedy algorithm

A brief review of the greedy algorithm for the Set-Cover problem.

# The algorithm

 input: collection of sets over universe , costs output: set cover 1. Let . 2. Repeat until is a set cover: 3. Find a set maximizing the number of elements in not yet covered by any set in , divided by the cost . 4. Add to . 5. Return .

# Performance guarantee

The following performance guarantee was proved in the 1970’s:

Theorem ([3, 4, 1]).

The greedy set-cover algorithm returns a set cover of cost at most , where is the minimum cost of any set cover, is the maximum set size, and is the th Harmonic number.

The guarantee actually holds with respect to the optimum fractional set cover. The proof is typically given as a charging argument, or by a primal-dual argument (constructing a related dual solution to bound opt).

The logarithmic approximation guarantee is the best possible in the following sense: if PNP, in the worst case, no polynomial-time algorithm guarantees a cover of cost , where is the number of elements to be covered [2].