Algorithms for NP-Hard Problems (Section 20.2: A Greedy Heuristic for Maximum Coverage) [Part 2/2]
Tim Roughgarden Lectures · 21:44
The greedy algorithm for maximum coverage is never guaranteed to be optimal, but for any input and any budget \(K\) it covers at least \(1-(1-1/K)^K\) of the best possible \(K\)-set coverage — 75% when \(K=2\), about...