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 monotone, submodular maximization over a groundset of size $n$ subject to cardinality constraint $k$. For this problem, weintroduce the first deterministic algorithms with linear time complexity; thesealgorithms are streaming algorithms. Our single-pass algorithm obtains aconstant ratio in $\lceil n / c \rceil + c$ oracle queries, for any $c \ge 1$.In addition, we propose a deterministic, multi-pass streaming algorithm with aconstant number of passes that achieves nearly the optimal ratio with linearquery and time complexities. We prove a lower bound that implies noconstant-factor approximation exists using $o(n)$ queries, even if queries toinfeasible sets are allowed. An empirical analysis demonstrates that ouralgorithms require fewer queries (often substantially less than $n$) yet stillachieve better objective value than the current state-of-the-art algorithms,including single-pass, multi-pass, and non-streaming algorithms.

Quick Streaming Algorithms for Maximization of Monotone Submodular Functions in Linear Time