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) - \ell(A) : A \in $\mathcal{F}$ }$,where$g \colon 2^\Omega \to $\mathbb{R}$+$isanon-monotonesubmodularfunction,$\ell \colon 2^\Omega \to $\mathbb{R}$+$isanormalizedmodularfunctionand$$\mathcal{F}$$ is the constraint set. Though the objective function $f:=g-\mathrm{\ell }$ 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-\mathrm{\ell }$ subject to a matroid constraint. Then, the pipage rounding procedure can produce an integral solution $S$ such that $$\mathbb{E}$ [g(S) - \ell(S)] \geq e^{-1}g(OPT) - \ell(OPT) - O(\epsilon)$. Moreover, we present a much faster algorithm for maximizing $g-\mathrm{\ell }$ subject to a cardinality constraint, which can output a solution $S$ with $$\mathbb{E}$ [g(S) - \ell(S)] \geq (e^{-1} - \epsilon) g(OPT)

• \ell(OPT)$using$O(\frac{n}{\epsilon^2} \ln \frac 1\epsilon)$ value oracle queries. We also consider the unconstrained maximization problem and give an algorithm which can return a solution $S$ with $$\mathbb{E}$ [g(S) - \ell(S)] \geq e^{-1} g(OPT) - \ell(OPT)$using$O(n)$ value oracle queries.