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 is a classic algorithmic problem with multipleapplications in data mining and machine learning; there, the growing need todeal with massive instances motivates the design of algorithms balancing thequality of the solution with applicability. For the latter, an importantmeasure is the adaptive complexity, which captures the number of sequentialrounds of parallel computation needed by an algorithm to terminate. In thiswork we obtain the first constant factor approximation algorithm fornon-monotone submodular maximization subject to a knapsack constraint withnear-optimal $O(\log n)$ adaptive complexity. Low adaptivity by itself,however, is not enough: a crucial feature to account for is represented by thetotal number of function evaluations (or value queries). Our algorithm asks$\tilde{O}(n^2)$ value queries, but can be modified to run with only$\tilde{O}(n)$ instead, while retaining a low adaptive complexity of$O(\log^2n)$. Besides the above improvement in adaptivity, this is also thefirst combinatorial approach with sublinear adaptive complexity for the problemand yields algorithms comparable to the state-of-the-art even for the specialcases of cardinality constraints or monotone objectives.

Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity