# On Maximizing Sums of Non-monotone Submodular and Linear Functions

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 May 2022.

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

- [Submodular Minimax Optimization: Finding Effective Sets](https://mlsanity.com/paper/2305.16903/) (2023)
- [Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint](https://mlsanity.com/paper/2405.13994/) (2024)
- [Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets](https://mlsanity.com/paper/2602.20578/) (2026)
- [Beyond Submodularity: A Unified Framework of Randomized Set Selection with Group Fairness Constraints](https://mlsanity.com/paper/2304.06596/) (2023)
- [GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility](https://mlsanity.com/paper/2405.18754/) (2024)
- [Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit](https://mlsanity.com/paper/2410.08578/) (2024)
- [Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions](https://mlsanity.com/paper/2605.07902/) (2026)

## Abstract (arXiv)

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].