Non-monotone submodular maximization with multiple knapsacks in static and dynamic settings
Date
2020
Authors
Doskoc, V.
Friedrich, T.
Göbel, A.
Neumann, A.
Neumann, F.
Quinzan, F.
Editors
Giacomo, G.D.
Catalá, A.
Dilkina, B.
Milano, M.
Barro, S.
Bugarín, A.
Lang, J.
Catalá, A.
Dilkina, B.
Milano, M.
Barro, S.
Bugarín, A.
Lang, J.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
International Journal of Computer Research, 2020 / Giacomo, G.D., Catalá, A., Dilkina, B., Milano, M., Barro, S., Bugarín, A., Lang, J. (ed./s), vol.325, pp.435-442
Statement of Responsibility
Vanja Doskoč, Tobias Friedrich, Andreas Göbel, Aneta Neumann, Frank Neumann, Francesco Quinzan
Conference Name
The 24th European Conference on Artificial Intelligence (ECAI) (29 Aug 2020 - 8 Sep 2020 : Santiago de Compostela, Spain)
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 does not require 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, in 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.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© 2020 The authors and IOS Press. This article is published online with Open Access by IOS Press and distributed under the terms of the Creative Commons Attribution Non-Commercial License 4.0 (CC BY-NC 4.0).