BriefGPT.xyz
Apr, 2019
超模极大化——非非负性保证、快速算法和应用
Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications
HTML
PDF
Christopher Harshaw, Moran Feldman, Justin Ward, Amin Karbasi
TL;DR
本文研究次模函数的优化和算法问题,提出了一种在 $k$-cardinality 约束下最大化 $g-c$ 的算法,并通过实验设计对其进行了验证。
Abstract
It is generally believed that
submodular functions
-- and the more general class of $\gamma$-weakly
submodular functions
-- may only be optimized under the non-negativity assumption $f(S) \geq 0$. In this paper,
→