Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity * - Archive ouverte HAL Access content directly
Conference Papers Year :

Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity *

(1, 2) , (3) , (3) , (3) , (3, 4) , (3)
1
2
3
4

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 adaptive complexity, capturing the number of sequential rounds of parallel computation needed. In this work we obtain the first constant factor approximation algorithm for non-monotone submodular maximization subject to a knapsack constraint with 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Õ(n 2) value queries, but can be modified to run with onlyÕ(n) instead, while retaining a low adaptive complexity of O(log 2 n). Besides the above improvement in adaptivity, this is also the first 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.
Fichier principal
Vignette du fichier
2102.08327.pdf (1013.88 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03474045 , version 1 (10-12-2021)

Identifiers

Cite

Georgios Amanatidis, Federico Fusco, Philip Lazos, Stefano Leonardi, Alberto Marchetti-Spaccamela, et al.. Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity *. ICML 2021 - 38th International Conference on Machine Learning, Jul 2021, Lugano, Italy. pp.1-25. ⟨hal-03474045⟩

Collections

INRIA INRIA2
23 View
55 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More