On Maximizing Sums of Non-monotone Submodular and Linear Functions
Benjamin Qi · Algorithmica · 2023
Abstract We study the problem of () as defined by Bodek and Feldman (Maximizing sums of non-monotone submodular and linear functions: understanding the unconstrained case, arXiv:2204.03412 , 2022): given query access to a non-negative submodular function $$f:2^{{\mathcal {N}}}\rightarrow {\mathbb {R}}_{\ge 0}$$ f : 2 N → R ≥ 0 and a linear function $$\ell :2^{{\mathcal {N}}}\rightarrow {\mathbb {R}}$$ ℓ : 2 N → R over the same ground set $${\mathcal {N}}$$ N , output a set $$T\subseteq {\mathcal {N}}$$ T ⊆ N approximately maximizing the sum $$f(T)+\ell (T)$$ f ( T ) + ℓ ( T ) . An algorithm is said to provide an $$(\alpha ,\beta )$$ ( α , β ) -approximation for if it outputs a set T such that $${\mathbb {E}}[f(T)+\ell (T)]\ge \max _{S\subseteq {\mathcal {N}}}[\alpha \cdot f(S)+\beta \cdot \ell (S)]$$ E [ f ( T ) + ℓ ( T ) ] ≥ max S ⊆ N [ α · f ( S ) + β · ℓ ( S ) ] . We also consider the setting where S and T are constrained to be independent in a given matroid, which we refer to as Constrained (). The special case of with monotone f has been extensively studied (Sviridenko et al. in Math Oper Res 42(4):1197–1218, 2017; Feldman in Algorithmica 83(3):853–878, 2021; Harshaw et al., in: International conference on machine learning, PMLR, 2634–2643, 2019), whereas we are aware of only one prior work that studies with non-monotone f (Lu et al. in Optimization 1–27, 2023), and that work constrains $$\ell $$ ℓ to be non-positive. In this work, we provide improved $$(\alpha ,\beta )$$ ( α , β )<