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

Maximizing a monotone submodular function under various constraints is aclassical and intensively studied problem. However, in the single-passstreaming model, where the elements arrive one by one and an algorithm canstore only a small fraction of input elements, there is much gap in ourknowledge, even though several approximation algorithms have been proposed inthe literature.  In this work, we present the first lower bound on the approximation ratiosfor cardinality and matroid constraints that beat $1-\frac{1}{e}$ in thesingle-pass streaming model. Let $n$ be the number of elements in the stream.Then, we prove that any (randomized) streaming algorithm for a cardinalityconstraint with approximation ratio $\frac{2}{2+\sqrt{2}}+\varepsilon$ requires$\Omega\left(\frac{n}{K^2}\right)$ space for any $\varepsilon>0$, where $K$ isthe size limit of the output set. We also prove that any (randomized) streamingalgorithm for a (partition) matroid constraint with approximation ratio$\frac{K}{2K-1}+\varepsilon$ requires $\Omega\left(\frac{n}{K}\right)$ spacefor any $\varepsilon>0$, where $K$ is the rank of the given matroid.  In addition, we give streaming algorithms when we only have a weak oraclewith which we can only evaluate function values on feasible sets. Specifically,we show weak-oracle streaming algorithms for cardinality and matroidconstraints with approximation ratios $\frac{K}{2K-1}$ and $\frac{1}{2}$,respectively, whose space complexity is exponential in $K$ but is independentof $n$. The former one exactly matches the known inapproximability result for acardinality constraint in the weak oracle model.  The latter one almost matches our lower bound of $\frac{K}{2K-1}$ for amatroid constraint, which almost settles the approximation ratio for a matroidconstraint that can be obtained by a streaming algorithm whose space complexityis independent of $n$.

Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model