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

Submodular maximization with a cardinality constraint can model variousproblems, and those problems are often very large in practice. For the casewhere objective functions are monotone, many fast approximation algorithms havebeen developed. The stochastic greedy algorithm (SG) is one such algorithm,which is widely used thanks to its simplicity, efficiency, and high empiricalperformance. However, its approximation guarantee has been proved only formonotone objective functions. When it comes to non-monotone objectivefunctions, existing approximation algorithms are inefficient relative to thefast algorithms developed for the case of monotone objectives. In this paper,we prove that SG (with slight modification) can achieve almost$1/4$-approximation guarantees in expectation in linear time even if objectivefunctions are non-monotone. Our result provides a constant-factor approximationalgorithm with the fewest oracle queries for non-monotone submodularmaximization with a cardinality constraint. Experiments validate theperformance of (modified) SG.

Guarantees of Stochastic Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraint