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/

Zendy Plus

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

Zendy Tools

Zendy Open

We consider parallel, or low adaptivity, algorithms for submodular functionmaximization. This line of work was recently initiated by Balkanski and Singerand has already led to several interesting results on the cardinalityconstraint and explicit packing constraints. An important open problem is theclassical setting of matroid constraint, which has been instrumental fordevelopments in submodular function maximization. In this paper we develop ageneral strategy to parallelize the well-studied greedy algorithm and use it toobtain a randomized $\left(\frac{1}{2} - \epsilon\right)$-approximation in$\operatorname{O}\left( \frac{\log^2 n}{\epsilon^2} \right)$ rounds ofadaptivity. We rely on this algorithm, and an elegant amplification approachdue to Badanidiyuru and Vondr\'ak to obtain a fractional solution that yields anear-optimal randomized $\left( 1 - 1/e - \epsilon \right)$-approximation in$O\left( {\frac{\log^2 n}{\epsilon^3}} \right) $ rounds of adaptivity. Fornon-negative functions we obtain a $\left( {3-2\sqrt{2}}\right)$-approximationand a fractional solution that yields a $\left( {\frac{1}{e} -\epsilon}\right)$-approximation. Our approach for parallelizing greedy yieldsapproximations for intersections of matroids and matchoids, and theapproximation ratios are comparable to those known for sequential greedy.

Parallelizing greedy for submodular set function maximization in matroids and beyond