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

DOI10.3233/FAIA200123MaRDI QIDQ4999249zbMATH OpenOpenAlexFDO

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

Publication date 6 July 2021

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

Mathematics Subject Classification ID

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

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.

Recommendations

• Non-monotone submodular maximization under matroid and knapsack constraints
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Maximizing a monotone non-submodular function under a knapsack constraint
• Maximization of nonsubmodular functions under multiple constraints with applications
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints

Cited in

(4)

• Pareto optimization for subset selection with dynamic cost constraints
• Multiple knapsack-constrained monotone DR-submodular maximization on distributive lattice -- continuous greedy algorithm on median complex --
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Non-monotone submodular maximization under matroid and knapsack constraints

This page was built for publication: Non-monotone submodular maximization with multiple knapsacks in static and dynamic settings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4999249)