Randomized greedy
Kent Quanrud · 74:12
The lecture shows that greedy maximization of a monotone submodular set function (e.g. maximum coverage with a cardinality constraint \(k\)) is a \((1-1/e)\)-approximation, and that dropping monotonicity requires a ra...