On Maximizing Sums of Non-monotone Submodular and Linear Functions
Benjamin Qi
Abstract
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}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>:</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>N</mml:mi> </mml:msup> <mml:mo>→</mml:mo> <mml:msub> <mml:mi>R</mml:mi> <mml:mrow> <mml:mo>≥</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> </mml:math> and a linear function $$\ell :2^{{\mathcal {N}}}\rightarrow {\mathbb {R}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ℓ</mml:mi> <mml:mo>:</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>N</mml:mi> </mml:msup> <mml:mo>→</mml:mo> <mml:mi>R</mml:mi> </mml:mrow> </mml:math> over the same ground set $${\mathcal {N}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>N</mml:mi> </mml:math> , output a set $$T\subseteq {\mathcal {N}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>T</mml:mi> <mml:mo>⊆</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> </mml:math> approximately maximizing the sum $$f(T)+\ell (T)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>(</mml:mo> <mml:mi>T</mml:mi> <mml:mo>)</mml:mo> <mml:mo>+</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>T</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . An algorithm is said to provide an $$(\alpha ,\beta )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>α</mml:mi> <mml:mo>,</mml:mo> <mml:mi>β</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -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)]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>E</mml:mi> <mml:mrow> <mml:mo>[</mml:mo> <mml:mi>f</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>T</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>+</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>T</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>]</mml:mo> </mml:mrow> <mml:mo>≥</mml:mo> <mml:msub> <mml:mo>max</mml:mo> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>⊆</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> </mml:msub> <mml:mrow> <mml:mo>[</mml:mo> <mml:mi>α</mml:mi> <mml:mo>·</mml:mo> <mml:mi>f</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>S</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>+</mml:mo> <mml:mi>β</mml:mi> <mml:mo>·</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>S</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>]</mml:mo> </mml:mrow> </mml:mrow> </mml:math> . 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 $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ℓ</mml:mi> </mml:math> to be non-positive. In this work, we provide improved $$(\alpha ,\beta )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>α</mml:mi> <mml:mo>,</mml:mo> <mml:mi>β</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -approximation algorithms for both and with non-monotone f . Specifically, we are the first to provide nontrivial $$(\alpha ,\beta )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>α</mml:mi> <mml:mo>,</mml:mo> <mml:mi>β</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -approximations for where the sign of $$\ell $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ℓ</mml:mi> </mml:math> is unconstrained, and the $$\alpha $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>α</mml:mi> </mml:math> we obtain for improves over (Bodek and Feldman in Maximizing sums of non-monotone submodular and linear functions: understanding the unconstrained case, arXiv:2204.03412 , 2022) for all $$\beta \in (0,1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>β</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>(</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . We also prove new inapproximability results for and , as well as 0.478-inapproximability for maximizing a submodular function where S and T are subject to a cardinality constraint, improving a 0.491-inapproximability result due to Oveis Gharan and Vondrak (in: Proceedings of the twenty-second annual ACM-SIAM symposium on discrete algorithms, SIAM, pp 1098–1116, 2011).