Timezone: »

Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity
Georgios Amanatidis · Federico Fusco · Philip Lazos · Stefano Leonardi · Alberto Marchetti-Spaccamela · Rebecca Reiffenhäuser

Tue Jul 20 06:40 PM -- 06:45 PM (PDT) @
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 $\tilde{O}(n^2)$ value queries, but can be modified to run with only $\tilde{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.

Author Information

Georgios Amanatidis (University of Essex)
Federico Fusco (Sapienza University of Rome)
Philip Lazos (Sapienza University of Rome)
Stefano Leonardi (Sapienza University of Rome)
Alberto Marchetti-Spaccamela (Sapienza University of Rome)
Rebecca Reiffenhäuser (Sapienza University of Rome)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors