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 prove that there is a randomized polynomial-time algorithm that given anedge-weighted graph $G$ excluding a fixed-minor $Q$ on $n$ vertices and anaccuracy parameter $\varepsilon>0$, constructs an edge-weighted graph~$H$ andan embedding $\eta\colon V(G)\to V(H)$ with the following properties: * For anyconstant size $Q$, the treewidth of $H$ is polynomial in $\varepsilon^{-1}$,$\log n$, and the logarithm of the stretch of the distance metric in $G$. * Theexpected multiplicative distortion is $(1+\varepsilon)$: for every pair ofvertices $u,v$ of $G$, we have $\mathrm{dist}_H(\eta(u),\eta(v))\geq\mathrm{dist}_G(u,v)$ always and$\mathrm{Exp}[\mathrm{dist}_H(\eta(u),\eta(v))]\leq(1+\varepsilon)\mathrm{dist}_G(u,v)$.  Our embedding is the first to achieve polylogarithmic treewidth of the hostgraph and comes close to the lower bound by Carroll and Goel, who showed thatany embedding of a planar graph with $\mathcal{O}(1)$ expected distortionrequires the host graph to have treewidth $\Omega(\log n)$. It also provides aunified framework for obtaining randomized quasi-polynomial-time approximationschemes for a variety of problems including network design, clustering orrouting problems, in minor-free metrics where the optimization goal is the sumof selected distances. Applications include the capacitated vehicle routingproblem, and capacitated clustering problems.

Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1