Regularized Non-monotone Submodular Maximization

In this paper, we present a thorough study of maximizing a regularized non-monotone submodular function subject to various constraints, i.e., max g(A) - ℓ(A) : A ∈ F , where g colon 2^Omega → ℝ_+ is a non-monotone submodular function, ℓ colon 2^Omega → ℝ_+ is a normalized modular function and F is the constraint set. Though the objective function f := g - ℓ is still submodular, the fact that f could potentially take on negative values prevents the existing methods for submodular maximization from providing a constant approximation ratio for the regularized submodular maximization problem. To overcome the obstacle, we propose several algorithms which can provide a relatively weak approximation guarantee for maximizing regularized non-monotone submodular functions. More specifically, we propose a continuous greedy algorithm for the relaxation of maximizing g - ℓ subject to a matroid constraint. Then, the pipage rounding procedure can produce an integral solution S such that mathbbE [g(S) - ℓ(S)] ≥ e-1g(OPT) - ℓ(OPT) - O(ε). Moreover, we present a much faster algorithm for maximizing g - ℓ subject to a cardinality constraint, which can output a solution S with mathbbE [g(S) - ℓ(S)] ≥ (e-1 - ε) g(OPT) - ℓ(OPT) using O(fracnε2 ln frac 1ε) value oracle queries. We also consider the unconstrained maximization problem and give an algorithm which can return a solution S with mathbbE [g(S) - ℓ(S)] ≥ e-1 g(OPT) - ℓ(OPT) using O(n) value oracle queries.