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.

Full Text: [PDF]

Accessibility at Yale   Inference, Information, and Decision Group at Yale