Maximizing Sums of Non-monotone Submodular and Linear Functions: Understanding the Unconstrained Case

Kobi Bodek, Moran Feldman

Motivated by practical applications, recent works have considered maximization of sums of a submodular function $g$ and a linear function $\ell$. Almost all such works, to date, st…