English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper we study the adaptivity of submodular maximization. Adaptivityquantifies the number of sequential rounds that an algorithm makes whenfunction evaluations can be executed in parallel. Adaptivity is a fundamentalconcept that is heavily studied across a variety of areas in computer science,largely due to the need for parallelizing computation. For the canonicalproblem of maximizing a monotone submodular function under a cardinalityconstraint, it is well known that a simple greedy algorithm achieves a $1-1/e$approximation and that this approximation is optimal for polynomial-timealgorithms. Somewhat surprisingly, despite extensive efforts on submodularoptimization for large-scale datasets, until very recently there was no knownalgorithm that achieves a constant factor approximation for this problem whoseadaptivity is sublinear in the size of the ground set $n$.  Recent work by Balkanski and Singer describes an algorithm that obtains anapproximation arbitrarily close to $1/3$ in $\mathcal{O}(\log n)$ adaptiverounds and shows that no algorithm can obtain a constant factor approximationin $\tilde{o}(\log n)$ adaptive rounds. This approach achieves an exponentialspeedup in adaptivity (and parallel running time) at the expense ofapproximation quality.  In this paper we describe a novel approach that yields an algorithm whoseapproximation is arbitrarily close to the optimal $1-1/e$ guarantee in$\mathcal{O}(\log n)$ adaptive rounds. This algorithm therefore achieves anexponential speedup in parallel running time for submodular maximization at theexpense of an arbitrarily small loss in approximation quality. This guaranteeis optimal in both approximation and adaptivity, up to lower order terms.

An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation