Regularized Non-monotone Submodular Maximization
share
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 ∈ℱ}, where g 2^Ω→ℝ_+ is a non-monotone submodular function, ℓ 2^Ω→ℝ_+ is a normalized modular function and ℱ 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 𝔼 [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 𝔼 [g(S) - ℓ(S)] ≥ (e^-1 - ϵ) g(OPT) - ℓ(OPT) using O(n/ϵ^2ln1/ϵ) value oracle queries. We also consider the unconstrained maximization problem and give an algorithm which can return a solution S with 𝔼 [g(S) - ℓ(S)] ≥ e^-1 g(OPT) - ℓ(OPT) using O(n) value oracle queries.
READ FULL TEXT