Set Cover

What is the fewest sets I can pick to cover all points?

The set cover problem takes an input which is a set of elements $B$, sets $S_1,\dots ,S_m\subset B$ and produces the fewest number of sets $S_i$, that cover all elements in $B$.

Applications:

• Information retrieval with redundancy
• Facility location This also uses Greedy Algorithms:

repeat until all elements in B are covered
	Pick the set S_i with the largest number of uncovered elements
end

The greedy algorithm uses $\le k\ln n$ sets. The gap between greedy and optimal grows slows as n grows. This is an approximation algorithm which runs in polynomial time and approximates the optimal solution within a provable factor. No further approximation algorithm exists for this problem currently.