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.

本研究提出了一种基于随机贪心算法解决非单调子模函数下的背包约束问题的方法，该算法实现了 5.83 近似和 O (nlogn) 时间复杂度；并将其转移到随机版本的问题，得到了首个非单调目标的常数近似，实验表明该方法在实际和合成数据上的性能得到了改进。