# Title: Greed Is Good: Near-Optimal Submodular Maximization via Greedy Optimization

# Authors: Moran Feldman, Christopher Harshaw, Amin Karbasi

# Abstract

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( k)-times leads to the (currently) fastest deterministic algorithm, called REPEATEDGREEDY, for maximizing a general submodular function subject to k-independent system constraints. REPEATEDGREEDY √√ achieves (1 + O(1/ k))k approximation using O(nr k) function evaluations (here, n and r de- note the size of the ground set and the maximum size of a feasible solution, respectively). We then show that by a careful sampling procedure, we can run the greedy algorithm only once and obtain the (currently) fastest randomized algorithm, called SAMPLEGREEDY, for maximizing a submodular function subject to k-extendible system constraints (a subclass of k-independent sys- tem constrains). SAMPLEGREEDY achieves (k + 3)-approximation with only O(nr/k) function evaluations. Finally, we derive an almost matching lower bound, and show that no polynomial time algorithm can have an approximation ratio smaller than k + 1/2 − ε. To further support our the- oretical results, we compare the performance of REPEATEDGREEDY and SAMPLEGREEDY with prior art in a concrete application (movie recommendation). We consistently observe that while SAMPLEGREEDY achieves practically the same utility as the best baseline, it performs at least two orders of magnitude faster.