Apr, 2018
近似最优化的子模最大化算法及其近线性时间自适应实现
Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
Alina Ene, Huy L. Nguyen
TL;DR本文研究了在满足基数约束的条件下,最大化单调子模函数的逼近保证和适应性之间的权衡问题。我们给出了第一个使用 O(lnn /epsilon^2)轮适应性实现 1-1 /e-epsilon 逼近的算法,同时算法的函数评估次数和额外运行时间分别为 O(npoly(logn,1 /epsilon))。