On Maximizing Sums of Non-monotone Submodular and Linear Functions

Benjamin Qi

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…