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

We develop a new framework for generalizing approximation algorithms from thestructural graph algorithm literature so that they apply to graphs somewhatclose to that class (a scenario we expect is common when working withreal-world networks) while still guaranteeing approximation ratios. The idea isto $\textit{edit}$ a given graph via vertex- or edge-deletions to put the graphinto an algorithmically tractable class, apply known approximation algorithmsfor that class, and then $\textit{lift}$ the solution to apply to the originalgraph. We give a general characterization of when an optimization problem isamenable to this approach, and show that it includes many well-studied graphproblems, such as Independent Set, Vertex Cover, Feedback Vertex Set, MinimumMaximal Matching, Chromatic Number, ($\ell$-)Dominating Set, Edge($\ell$-)Dominating Set, and Connected Dominating Set.  To enable this framework, we develop new editing algorithms that find theapproximately-fewest edits required to bring a given graph into one of severalimportant graph classes (in some cases, also approximating the target parameterof the family). For bounded degeneracy, we obtain a bicriteria$(4,4)$-approximation which also extends to a smoother bicriteria trade-off.For bounded treewidth, we obtain a bicriteria $(O(\log^{1.5} n), O(\sqrt{\logw}))$-approximation, and for bounded pathwidth, we obtain a bicriteria$(O(\log^{1.5} n), O(\sqrt{\log w} \cdot \log n))$-approximation. For treedepth$2$ (also related to bounded expansion), we obtain a $4$-approximation. We alsoprove complementary hardness-of-approximation results assuming $\mathrm{P} \neq\mathrm{NP}$: in particular, these problems are all log-factor inapproximable,except the last which is not approximable below some constant factor ($2$assuming UGC).

Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class