论文标题
快速自适应非单调性supdodular最大化受背包约束
Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
论文作者
论文摘要
受限制的少量最大化问题涵盖了各种各样的应用程序，包括个性化建议，团队形成和通过病毒营销的收入最大化。现代应用中发生的大规模实例可以使现有的算法过慢地变慢，而这些实例经常是天生的随机算法。为了关注这些挑战，我们重新审视了受背包约束（可能是非单调的）下一个函数（可能是非单调的）函数的经典问题。我们提出了一种简单的随机贪婪算法，可实现$ 5.83 $的近似值，并以$ O（n \ log n）$时间运行，即至少比其他最先进的算法更快。我们方法的鲁棒性使我们能够将其进一步转移到问题的随机版本中。在那里，我们获得了最佳自适应策略的9个应用，这是非单调目标的第一个常数近似值。我们算法的实验评估展示了它们在实际和合成数据上的提高性能。
Constrained submodular maximization problems encompass a wide variety of applications, including personalized recommendation, team formation, and revenue maximization via viral marketing. The massive instances occurring in modern day applications can render existing algorithms prohibitively slow, while frequently, those instances are also inherently stochastic. Focusing on these challenges, we revisit the classic problem of maximizing a (possibly non-monotone) submodular function subject to a knapsack constraint. We present a simple randomized greedy algorithm that achieves a $5.83$ approximation and runs in $O(n \log n)$ time, i.e., at least a factor $n$ faster than other state-of-the-art algorithms. The robustness of our approach allows us to further transfer it to a stochastic version of the problem. There, we obtain a 9-approximation to the best adaptive policy, which is the first constant approximation for non-monotone objectives. Experimental evaluation of our algorithms showcases their improved performance on real and synthetic data.
