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

Maximization of {\it non-submodular} functions appears in various scenarios,and many previous works studied it based on some measures that quantify thecloseness to being submodular. On the other hand, many practical non-submodularfunctions are actually close to being {\it modular}, which has been utilized infew studies. In this paper, we study cardinality-constrained maximization of{\it weakly modular} functions, whose closeness to being modular is measured by{\it submodularity} and {\it supermodularity ratios}, and reveal what we canand cannot do by using the weak modularity. We first show that guarantees ofmulti-stage algorithms can be proved with the weak modularity, which generalizeand improve some existing results, and experiments confirm their effectiveness.We then show that weakly modular maximization is {\it fixed-parametertractable} under certain conditions; as a byproduct, we provide a newtime--accuracy trade-off for $\ell_0$-constrained minimization. We finallyprove that, even if objective functions are weakly modular, no polynomial-timealgorithms can improve the existing approximation guarantees achieved by thegreedy algorithm.

On Maximization of Weakly Modular Functions: Guarantees of Multi-stage Algorithms, Tractability, and Hardness