论文标题
最大化非单调的非单调性函数，超过$ 1/2 $ - APPROXIMATION
Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond $1/2$-Approximation
论文作者
论文摘要
在这项工作中，我们给出了两种新算法，这些算法使用类似的技术对（非单调性）下一个函数最大化受到基数约束。 第一个是脱机固定参数可处理算法，可保证所有非负subpoular函数的$ 0.539 $ APPRXIMATION。 第二算法在随机阶流模型中起作用。它保证了对称函数的$（1/2+c）$ - 近似值，我们通过证明没有空间效率的算法可以比非对称功能击败$ 1/2 $来对其进行补充。据我们所知，这是对称和非对称下函数最大化之间的第一个可证明的分离。
In this work we give two new algorithms that use similar techniques for (non-monotone) submodular function maximization subject to a cardinality constraint. The first is an offline fixed parameter tractable algorithm that guarantees a $0.539$-approximation for all non-negative submodular functions. The second algorithm works in the random-order streaming model. It guarantees a $(1/2+c)$-approximation for symmetric functions, and we complement it by showing that no space-efficient algorithm can beat $1/2$ for asymmetric functions. To the best of our knowledge this is the first provable separation between symmetric and asymmetric submodular function maximization.
