Non-monotone submodular maximization with multiple knapsacks in static and dynamic settings

DOI10.3233/FAIA200123zbMATH Open1464.90075arXiv1911.06791OpenAlexW3090397044MaRDI QIDQ4999249

Francesco Quinzan, F. Neumann, Aneta Neumann, Andreas Göbel, Tobias Friedrich, Vanja Doskoč

Publication date: 6 July 2021

Abstract: We study the problem of maximizing a non-monotone submodular function under multiple knapsack constraints. We propose a simple discrete greedy algorithm to approach this problem, and prove that it yields strong approximation guarantees for functions with bounded curvature. In contrast to other heuristics, this requires no problem relaxation to continuous domains and it maintains a constant-factor approximation guarantee in the problem size. In the case of a single knapsack, our analysis suggests that the standard greedy can be used in non-monotone settings. Additionally, we study this problem in a dynamic setting, by which knapsacks change during the optimization process. We modify our greedy algorithm to avoid a complete restart at each constraint update. This modification retains the approximation guarantees of the static case. We evaluate our results experimentally on a video summarization and sensor placement task. We show that our proposed algorithm competes with the state-of-the-art in static settings. Furthermore, we show that in dynamic settings with tight computational time budget, our modified greedy yields significant improvements over starting the greedy from scratch, in terms of the solution quality achieved.

Full work available at URL: https://arxiv.org/abs/1911.06791

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)