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.
Dettaglio pubblicazione
2021, Proceedings of the 38th International Conference on Machine Learning, Pages 231-242 (volume: 139)
Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity (04b Atto di convegno in volume)
Amanatidis Georgios, Fusco Federico, Lazos Filippos, Leonardi Stefano, Marchetti-Spaccamela Alberto, Rebecca Reiffenhäuser
Gruppo di ricerca: Algorithms and Data Science
keywords