Maximizing non-monotone submodular functions

Submodular maximization generalizes many important problems including Max Cut in directed/undirected graphs and hypergraphs, certain constraint satisfaction problems and maximum facility location problems. Unlike the problem of minimizing submodular functions, the problem of maximizing submodular functions is NP-hard. In this paper we design the first constant-factor approximation algorithms for maximizing nonnegative submodular functions. In particular we give a deterministic local search 1/3-approximation and a randomized 2/5-approximation algorithm for maximizing nonnegative submodular functions. We also show that a uniformly random set gives a 1/4-approximation. For symmetric submodular functions, we show that a random set gives a 1/2-approximation, which can 2 be also achieved by deterministic local search. These algorithms work in the value oracle model where the submodular function is accessible through a black box returning f(S) for a given set S. We show that in this model, 1/2-Lapproximation for symmetric submodular functions is the best one can achieve with a subexponential number of queries. For the case where the function is given explicitly (as a sum of nonnegative submodular functions, each depending only on a constant number of elements), we prove that it is NP-hard to achieve a (3/4 + epsilon)-approximation 4 in the general case (or a 5/6 + epsilon)-approximation in the symmetric case).