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

Motivated by practical applications, recent works have consideredmaximization of sums of a submodular function $g$ and a linear function $\ell$.Almost all such works, to date, studied only the special case of this problemin which $g$ is also guaranteed to be monotone. Therefore, in this paper wesystematically study the simplest version of this problem in which $g$ isallowed to be non-monotone, namely the unconstrained variant, which we termRegularized Unconstrained Submodular Maximization (RegularizedUSM).  Our main algorithmic result is the first non-trivial guarantee for generalRegularizedUSM. For the special case of RegularizedUSM in which the linearfunction $\ell$ is non-positive, we prove two inapproximability results,showing that the algorithmic result implied for this case by previous works isnot far from optimal. Finally, we reanalyze the known Double Greedy algorithmto obtain improved guarantees for the special case of RegularizedUSM in whichthe linear function $\ell$ is non-negative; and we complement these guaranteesby showing that it is not possible to obtain (1/2, 1)-approximation for thiscase (despite intuitive arguments suggesting that this approximation guaranteeis natural).

Maximizing Sums of Non-monotone Submodular and Linear Functions: Understanding the Unconstrained Case