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

We consider the problem of maximizing the multilinear extension of asubmodular function subject a single matroid constraint or multiple packingconstraints with a small number of adaptive rounds of evaluation queries.  We obtain the first algorithms with low adaptivity for submodularmaximization with a matroid constraint. Our algorithms achieve a$1-1/e-\epsilon$ approximation for monotone functions and a $1/e-\epsilon$approximation for non-monotone functions, which nearly matches the bestguarantees known in the fully adaptive setting. The number of rounds ofadaptivity is $O(\log^2{n}/\epsilon^3)$, which is an exponential speedup overthe existing algorithms.  We obtain the first parallel algorithm for non-monotone submodularmaximization subject to packing constraints. Our algorithm achieves a$1/e-\epsilon$ approximation using $O(\log(n/\epsilon) \log(1/\epsilon)\log(n+m)/ \epsilon^2)$ parallel rounds, which is again an exponential speedupin parallel time over the existing algorithms. For monotone functions, weobtain a $1-1/e-\epsilon$ approximation in$O(\log(n/\epsilon)\log(m)/\epsilon^2)$ parallel rounds. The number of parallelrounds of our algorithm matches that of the state of the art algorithm forsolving packing LPs with a linear objective.  Our results apply more generally to the problem of maximizing a diminishingreturns submodular (DR-submodular) function.

Submodular Maximization with Matroid and Packing Constraints in Parallel