# Regularized Non-monotone Submodular Maximization

arXiv: https://arxiv.org/abs/2103.10008 · HTML: https://mlsanity.com/paper/2103.10008/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Mar 2021.

## Built on by (most cited first, 1 of 1)

- [Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions](https://mlsanity.com/paper/2605.07902/) (2026)

## Abstract (arXiv)

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.