论文标题
使用局部下义比弱的弱下功能最大化
Weakly Submodular Function Maximization Using Local Submodularity Ratio
论文作者
论文摘要
弱下性是自然放松的返回特性，这等同于下型。较弱的下二次性已被用来表明在实践中出现的许多（单调）功能可以有效地最大化，并具有可证明的保证。在这项工作中，我们介绍了两个自然概括的非单向酮功能的自然概括。我们表明，有效的随机贪婪算法可证明可以保证受到基数约束的最大化。然后，我们提供了一个更精致的分析，该分析考虑到整个算法的执行过程中弱的子二次参数可能会改变（有时会改善）。在某些情况下，这可以改善近似值。我们为单调和非符号酮最大化问题提供了结果的应用。
Weak submodularity is a natural relaxation of the diminishing return property, which is equivalent to submodularity. Weak submodularity has been used to show that many (monotone) functions that arise in practice can be efficiently maximized with provable guarantees. In this work we introduce two natural generalizations of weak submodularity for non-monotone functions. We show that an efficient randomized greedy algorithm has provable approximation guarantees for maximizing these functions subject to a cardinality constraint. We then provide a more refined analysis that takes into account that the weak submodularity parameter may change (sometimes improving) throughout the execution of the algorithm. This leads to improved approximation guarantees in some settings. We provide applications of our results for monotone and non-monotone maximization problems.
