2020
On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness
ICML 2020poster
It is well known that the standard greedy algorithm guarantees a worst-case approximation factor of $1-1/e$ when maximizing a monotone submodular function under a cardinality constraint. However, empirical studies show that its performance is substantially better in practice. This raises a natural q…