Greedy approximations
Kent Quanrud · 9:18
The video proves that the greedy algorithm for the maximum-coverage problem—pick \(K\) sets one at a time, always taking the set that covers the most still-uncovered points—is a \((1-1/e)\)-approximation: its coverage...