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

Simple item page
dc.contributor.authorDoskoc, V.
dc.contributor.authorFriedrich, T.
dc.contributor.authorGöbel, A.
dc.contributor.authorNeumann, A.
dc.contributor.authorNeumann, F.
dc.contributor.authorQuinzan, F.
dc.contributor.conferenceThe 24th European Conference on Artificial Intelligence (ECAI) (29 Aug 2020 - 8 Sep 2020 : Santiago de Compostela, Spain)
dc.contributor.editorGiacomo, G.D.
dc.contributor.editorCatalá, A.
dc.contributor.editorDilkina, B.
dc.contributor.editorMilano, M.
dc.contributor.editorBarro, S.
dc.contributor.editorBugarín, A.
dc.contributor.editorLang, J.
dc.date.issued2020
dc.description.abstractWe 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.
dc.description.statementofresponsibilityVanja Doskoč, Tobias Friedrich, Andreas Göbel, Aneta Neumann, Frank Neumann, Francesco Quinzan
dc.identifier.citationInternational 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
dc.identifier.doi10.3233/FAIA200123
dc.identifier.isbn9781643681009
dc.identifier.issn0922-6389
dc.identifier.issn1879-8314
dc.identifier.orcidNeumann, A. [0000-0002-0036-4782]
dc.identifier.orcidNeumann, F. [0000-0002-2721-3618]
dc.identifier.urihttp://hdl.handle.net/2440/131963
dc.language.isoen
dc.publisherIOS Press
dc.publisher.placeAmsterdam, Netherlands
dc.relation.granthttp://purl.org/au-research/grants/arc/DP160102401
dc.relation.ispartofseriesFrontiers in Artificial Intelligence and Applications; 325
dc.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).
dc.source.urihttps://ebooks.iospress.nl/volume/ecai-2020-24th-european-conference-on-artificial-intelligence
dc.titleNon-monotone submodular maximization with multiple knapsacks in static and dynamic settings
dc.typeConference paper
pubs.publication-statusPublished

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
hdl_131963.pdf
Size:
320.5 KB
Format:
Adobe Portable Document Format
Download

Collections

Computer Science publications