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

Maximum weight independent set (MWIS) admits a $\frac1k$-approximation ininductively $k$-independent graphs and a $\frac{1}{2k}$-approximation in$k$-perfectly orientable graphs. These are a a parameterized class of graphsthat generalize $k$-degenerate graphs, chordal graphs, and intersection graphsof various geometric shapes such as intervals, pseudo-disks, and severalothers. We consider a generalization of MWIS to a submodular objective. Given agraph $G=(V,E)$ and a non-negative submodular function $f: 2^V \rightarrow\mathbb{R}_+$, the goal is to approximately solve $\max_{S \in \mathcal{I}_G}f(S)$ where $\mathcal{I}_G$ is the set of independent sets of $G$. We obtain an$\Omega(\frac1k)$-approximation for this problem in the two mentioned graphclasses. The first approach is via the multilinear relaxation framework and asimple contention resolution scheme, and this results in a randomized algorithmwith approximation ratio at least $\frac{1}{e(k+1)}$. This approach also yieldsparallel (or low-adaptivity) approximations. Motivated by the goal of designingefficient and deterministic algorithms, we describe two other algorithms forinductively $k$-independent graphs that are inspired by work on streamingalgorithms: a preemptive greedy algorithm and a primal-dual algorithm. Inaddition to being simpler and faster, these algorithms, in the monotonesubmodular case, yield the first deterministic constant factor approximationsfor various special cases that have been previously considered such asintersection graphs of intervals, disks and pseudo-disks.

Independent Sets in Elimination Graphs with a Submodular Objective