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

Constrained submodular maximization problems encompass a wide variety ofapplications, including personalized recommendation, team formation, andrevenue maximization via viral marketing. The massive instances occurring inmodern day applications can render existing algorithms prohibitively slow,while frequently, those instances are also inherently stochastic. Focusing onthese challenges, we revisit the classic problem of maximizing a (possiblynon-monotone) submodular function subject to a knapsack constraint. We presenta simple randomized greedy algorithm that achieves a $5.83$ approximation andruns in $O(n \log n)$ time, i.e., at least a factor $n$ faster than otherstate-of-the-art algorithms. The robustness of our approach allows us tofurther transfer it to a stochastic version of the problem. There, we obtain a9-approximation to the best adaptive policy, which is the first constantapproximation for non-monotone objectives. Experimental evaluation of ouralgorithms showcases their improved performance on real and synthetic data.

Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint