The growing need to deal with massive instances motivates the design of algorithms balancing the quality of the solution with applicability. For the latter, an important measure is the emph{adaptive complexity}, capturing the number of sequential rounds of parallel computation needed. In this work we obtain the first emph{constant factor} approximation algorithm for non-monotone submodular maximization subject to a knapsack constraint with emph{near-optimal} $O(log n)$ adaptive complexity. Low adaptivity by itself, however, is not enough: one needs to account for the total number of function evaluations (or value queries) as well. Our algorithm asks $ ilde{O}(n^2)$ value queries, but can be modified to run with only $ ilde{O}(n)$ instead, while retaining a low adaptive complexity of $O(log^2n)$. Besides the above improvement in adaptivity, this is also the first emph{combinatorial} approach with sublinear adaptive complexity for the problem and yields algorithms comparable to the state-of-the-art even for the special cases of cardinality constraints or monotone objectives. Finally, we showcase our algorithms’ applicability on real-world datasets.

Submodular maximization subject to a knapsack constraint: combinatorial algorithms with near-optimal adaptive complexity / Amanatidis, Georgios; Fusco, Federico; Lazos, Filippos; Leonardi, Stefano; MARCHETTI SPACCAMELA, Alberto; Reiffenhäuser, Rebecca. - 139:(2021), pp. 231-242. (Intervento presentato al convegno International Conference on Machine Learning tenutosi a Virtuale).

Submodular maximization subject to a knapsack constraint: combinatorial algorithms with near-optimal adaptive complexity

Amanatidis Georgios;Federico Fusco
;
Lazos Filippos;Leonardi Stefano;Marchetti-Spaccamela Alberto;Rebecca Reiffenhäuser
2021

Abstract

The growing need to deal with massive instances motivates the design of algorithms balancing the quality of the solution with applicability. For the latter, an important measure is the emph{adaptive complexity}, capturing the number of sequential rounds of parallel computation needed. In this work we obtain the first emph{constant factor} approximation algorithm for non-monotone submodular maximization subject to a knapsack constraint with emph{near-optimal} $O(log n)$ adaptive complexity. Low adaptivity by itself, however, is not enough: one needs to account for the total number of function evaluations (or value queries) as well. Our algorithm asks $ ilde{O}(n^2)$ value queries, but can be modified to run with only $ ilde{O}(n)$ instead, while retaining a low adaptive complexity of $O(log^2n)$. Besides the above improvement in adaptivity, this is also the first emph{combinatorial} approach with sublinear adaptive complexity for the problem and yields algorithms comparable to the state-of-the-art even for the special cases of cardinality constraints or monotone objectives. Finally, we showcase our algorithms’ applicability on real-world datasets.
2021
International Conference on Machine Learning
Submodular mazimization; combinatorial algorithms; adaptive complexity
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Submodular maximization subject to a knapsack constraint: combinatorial algorithms with near-optimal adaptive complexity / Amanatidis, Georgios; Fusco, Federico; Lazos, Filippos; Leonardi, Stefano; MARCHETTI SPACCAMELA, Alberto; Reiffenhäuser, Rebecca. - 139:(2021), pp. 231-242. (Intervento presentato al convegno International Conference on Machine Learning tenutosi a Virtuale).
File allegati a questo prodotto
File Dimensione Formato  
Amanatidis_Submodular_2021.pdf

accesso aperto

Note: http://proceedings.mlr.press/v139/amanatidis21a/amanatidis21a.pdf
Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 759.12 kB
Formato Adobe PDF
759.12 kB Adobe PDF
Amanatidis_Supp_Submodular_2021.pdf

accesso aperto

Note: http://proceedings.mlr.press/v139/amanatidis21a/amanatidis21a-supp.pdf
Tipologia: Altro materiale allegato
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 277.56 kB
Formato Adobe PDF
277.56 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1598785
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 0
social impact