论文标题
关于最大化非单调子模块和线性函数的总和
On Maximizing Sums of Non-monotone Submodular and Linear Functions
论文作者
论文摘要
我们研究了由Bodek和Feldman [BF22]定义的正规化无约束的下二个最大化（正则化）的问题。在此问题中，给您一个非单调的非负subsodular函数$ f：2^{\ mathcal n} \ to \ Mathbb r _ {\ ge 0} $和线性函数$ \ ell：2^{\ Mathcal n} $ t \ subseteq \ mathcal n $大约最大化$ f（t）+\ ell（t）$。具体而言，据说算法可以为正则usm提供$（α，β）$ - 近似值，如果它输出$ t $，以至于$ \ mathbb e [f（t）+\ ell（t）] \ ge \ ge \ ge \ max_ {s \ subSeteq \ subseteq \ subseteeq \ mathcal n} [α\ cdot f（s）$β]我们还研究了$ s $和$ t $的设置，受到矩阵约束的约束，我们称之为正规化的受约束的supproumardular最大化（正则CSM）。 对于正则usm和正则化csm，我们为非阳性$ \ ell $，非负$ \ ell $的$（α，β）$ - 近似算法提供了改进的$（α，β）$ - 近似算法。特别是，对于不受限制的$ \ ell $，我们是第一个为正则csm提供非平凡$（α，β）$ - 近似值的人，而我们为正则usef提供的$α$优于[bf22]的$β\ in（0,1）$。 除了近似算法外，我们还为所有上述情况提供了改进的不Xibibibibility结果。特别是，我们表明，我们的算法$α$对于未约束的$ \ ell $获得的正则化算法对于$β\ ge \ frac {e} {e+1} $很紧。我们还显示了0.478-抗Xibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibliabiability optabibibibibibibibibibliagiabilability optabibibibibiausiabilitians $ s $和$ t $在$ S $和$ t $中受到基数约束的约束，从而改善了由于Gharan和Vondrak [GV10]而导致的长期存在的0.491-耐Ximability结果。
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:2^{\mathcal N}\to \mathbb R_{\ge 0}$ and a linear function $\ell:2^{\mathcal N}\to \mathbb R$ over the same ground set $\mathcal N$, and the objective is to output a set $T\subseteq \mathcal N$ approximately maximizing the sum $f(T)+\ell(T)$. Specifically, an algorithm is said to provide an $(α,β)$-approximation for RegularizedUSM if it outputs a set $T$ such that $\mathbb E[f(T)+\ell(T)]\ge \max_{S\subseteq \mathcal N}[α\cdot f(S)+β\cdot \ell(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 $\ell$, non-negative $\ell$, and unconstrained $\ell$. In particular, for the case of unconstrained $\ell$, we are the first to provide nontrivial $(α,β)$-approximations for RegularizedCSM, and the $α$ we obtain for RegularizedUSM is superior to that of [BF22] for all $β\in (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 $\ell$ is tight for $β\ge \frac{e}{e+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].
