On Maximizing Sums of Non-monotone Submodular and Linear Functions

We study the problem of Regularized Unconstrained Submodular Maximization (RegularizedUSM) as defined by Bodek and Feldman [BF22]. In this problem, you are given a non-monotone non-negative submodular function f:2mathcal N→ mathbb R≥ 0 and a linear function ℓ:2mathcal N→ mathbb R over the same ground set mathcal N, and the objective is to output a set Tsubseteq mathcal N approximately maximizing the sum f(T)+ℓ(T). Specifically, an algorithm is said to provide an (α,β)-approximation for RegularizedUSM if it outputs a set T such that mathbb E[f(T)+ℓ(T)]≥ maxSsubseteq mathcal N[α · f(S)+β· ℓ(S)]. We also study the setting where S and T are subject to a matroid constraint, which we refer to as Regularized Constrained Submodular Maximization (RegularizedCSM). For both RegularizedUSM and RegularizedCSM, we provide improved (α,β)-approximation algorithms for the cases of non-positive ℓ, non-negative ℓ, and unconstrained ℓ. In particular, for the case of unconstrained ℓ, we are the first to provide nontrivial (α,β)-approximations for RegularizedCSM, and the α we obtain for RegularizedUSM is superior to that of [BF22] for all β∈ (0,1). In addition to approximation algorithms, we provide improved inapproximability results for all of the aforementioned cases. In particular, we show that the α our algorithm obtains for RegularizedCSM with unconstrained ℓ is tight for β≥ fracee+1. We also show 0.478-inapproximability for maximizing a submodular function where S and T are subject to a cardinality constraint, improving the long-standing 0.491-inapproximability result due to Gharan and Vondrak [GV10].