Jul, 2020
针对背包约束的快速自适应非单调子模型最大化
Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
Georgios Amanatidis, Federico Fusco, Philip Lazos, Stefano Leonardi, Rebecca Reiffenhäuser
TL;DR本研究提出了一种基于随机贪心算法解决非单调子模函数下的背包约束问题的方法,该算法实现了 5.83 近似和 O (nlogn) 时间复杂度;并将其转移到随机版本的问题,得到了首个非单调目标的常数近似,实验表明该方法在实际和合成数据上的性能得到了改进。