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 give improved multi-pass streaming algorithms for the problem ofmaximizing a monotone or arbitrary non-negative submodular function subject toa general $p$-matchoid constraint in the model in which elements of the groundset arrive one at a time in a stream. The family of constraints we considergeneralizes both the intersection of $p$ arbitrary matroid constraints and$p$-uniform hypergraph matching. For monotone submodular functions, ouralgorithm attains a guarantee of $p+1+\varepsilon$ using$O(p/\varepsilon)$-passes and requires storing only $O(k)$ elements, where $k$is the maximum size of feasible solution. This immediately gives an$O(1/\varepsilon)$-pass $(2+\varepsilon)$-approximation algorithms for monotonesubmodular maximization in a matroid and $(3+\varepsilon)$-approximation formonotone submodular matching. Our algorithm is oblivious to the choice$\varepsilon$ and can be stopped after any number of passes, delivering theappropriate guarantee. We extend our techniques to obtain the first multi-passstreaming algorithm for general, non-negative submodular functions subject to a$p$-matchoid constraint with a number of passes independent of the size of theground set and $k$. We show that a randomized $O(p/\varepsilon)$-pass algorithmstoring $O(p^3k\log(k)/\varepsilon^3)$ elements gives a$(p+1+\bar{\gamma}+O(\varepsilon))$-approximation, where $\bar{gamma}$ is theguarantee of the best-known offline algorithm for the same problem.

Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints