Research Repository

Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint

Amanatidis, Georgios and Fusco, Federico and Lazos, Philip and Leonardi, Stefano and Reiffenhäuser, Rebecca (2022) 'Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint.' Journal of Artificial Intelligence Research, 74. pp. 661-690. ISSN 1076-9757

13472-Article (PDF)-30833-1-10-20220609.pdf - Published Version

Download (494kB) | Preview


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 versatility 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.

Item Type: Article
Uncontrolled Keywords: uncertainty, machine learning
Divisions: Faculty of Science and Health
Faculty of Science and Health > Mathematical Sciences, Department of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 21 Jun 2022 15:59
Last Modified: 23 Sep 2022 19:53

Actions (login required)

View Item View Item