论文标题
最大化非符号酮子管函数和线性函数的总和：理解无约束的情况
Maximizing Sums of Non-monotone Submodular and Linear Functions: Understanding the Unconstrained Case
论文作者
论文摘要
在实际应用程序的激励下，最近的作品考虑了$ g $和线性函数$ \ ell $的总和的最大化。迄今为止，几乎所有这些工作仅研究了此问题的特殊情况，其中$ g $也保证为单调。因此，在本文中，我们系统地研究了该问题的最简单版本，其中$ g $被允许为非单调酮，即无约束的变体，我们将其称为正规化的无约束的supprodular最大化（正则化使用）。 我们的主要算法结果是通用正则化uSM的第一个非平凡保证。对于正规函数的特殊情况，即线性函数$ \ ell $是非阳性的，我们证明了两个无Ximibibility结果，表明先前的作品对这种情况暗示的算法结果远非最佳。最后，我们将已知的双贪婪算法重新分析，以获得正规函数$ \ ell $不负的特殊情况的改进保证；我们通过表明无法获得（1/2，1）对这种情况的及时（尽管有直觉的论点表明这种近似保证是自然的）来补充这些保证。
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, studied only the special case of this problem in which $g$ is also guaranteed to be monotone. Therefore, in this paper we systematically study the simplest version of this problem in which $g$ is allowed to be non-monotone, namely the unconstrained variant, which we term Regularized Unconstrained Submodular Maximization (RegularizedUSM). Our main algorithmic result is the first non-trivial guarantee for general RegularizedUSM. For the special case of RegularizedUSM in which the linear function $\ell$ is non-positive, we prove two inapproximability results, showing that the algorithmic result implied for this case by previous works is not far from optimal. Finally, we reanalyze the known Double Greedy algorithm to obtain improved guarantees for the special case of RegularizedUSM in which the linear function $\ell$ is non-negative; and we complement these guarantees by showing that it is not possible to obtain (1/2, 1)-approximation for this case (despite intuitive arguments suggesting that this approximation guarantee is natural).
