Greed is Good: Near-Optimal Submodular Maximization via Greedy Optimization

Understand

It is known that greedy methods perform well for maximizing monotone submodular functions.

• At the same time, such methods perform poorly in the face of non-monotonicity.
• In this paper, we show - arguably, surprisingly - that invoking the classical greedy algorithm $O(\sqrt{k})$-times leads to the (currently) fastest deterministic algorithm, called Repeated Greedy, for maximizing a general submodular function subject to $k$-independent system constraints.
• Repeated Greedy achieves $(1 + O(1/\sqrt{k}))k$ approximation using $O(nr\sqrt{k})$ function evaluations (here, $n$ and $r$ denote the size of the ground set and the maximum size of a feasible solution, respectively).