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/{\sqrt{k}}))k$ approximation using $O(nr \sqrt{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