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/

Zendy Plus

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

Zendy Tools

Zendy Open

We investigate the existence of approximation algorithms for maximization ofsubmodular functions, that run in fixed parameter tractable (FPT) time. Given anon-decreasing submodular set function $v: 2^X \to \mathbb{R}$ the goal is toselect a subset $S$ of $K$ elements from $X$ such that $v(S)$ is maximized. Weidentify three properties of set functions, referred to as $p$-separabilityproperties, and we argue that many real-life problems can be expressed asmaximization of submodular, $p$-separable functions, with low values of theparameter $p$. We present FPT approximation schemes for the minimization andmaximization variants of the problem, for several parameters that depend oncharacteristics of the optimized set function, such as $p$ and $K$. We confirmthat our algorithms are applicable to a broad class of problems, in particularto problems from computational social choice, such as item selection or winnerdetermination under several multiwinner election systems.

FPT Approximation Schemes for Maximizing Submodular Functions