Timezone: »

Poster
Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
Georgios Amanatidis · Federico Fusco · Philip Lazos · Stefano Leonardi · Rebecca Reiffenhäuser

Tue Dec 08 09:00 AM -- 11:00 AM (PST) @ Poster Session 1 #514
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. Moreover, 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.