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

Cohen-Addad, Filtser, Klein and Le [FOCS'20] constructed a stochasticembedding of minor-free graphs of diameter $D$ into graphs of treewidth$O_{\epsilon}(\log n)$ with expected additive distortion $+\epsilon D$.Cohen-Addad et al. then used the embedding to design the first quasi-polynomialtime approximation scheme (QPTAS) for the capacitated vehicle routing problem.Filtser and Le [STOC'21] used the embedding (in a different way) to design aQPTAS for the metric Baker's problems in minor-free graphs. In this work, wedevise a new embedding technique to improve the treewidth bound of Cohen-Addadet al. exponentially to $O_{\epsilon}(\log\log n)^2$. As a corollary, we obtainthe first efficient PTAS for the capacitated vehicle routing problem inminor-free graphs. We also significantly improve the running time of the QPTASfor the metric Baker's problems in minor-free graphs from$n^{O_{\epsilon}(\log(n))}$ to $n^{O_{\epsilon}(\log\log(n))^3}$.  Applying our embedding technique to planar graphs, we obtain a deterministicembedding of planar graphs of diameter $D$ into graphs of treewidth$O((\log\log n)^2)/\epsilon)$ and additive distortion $+\epsilon D$ that can beconstructed in nearly linear time. Important corollaries of our result includea bicriteria PTAS for metric Baker's problems and a PTAS for the vehiclerouting problem with bounded capacity in planar graphs, both run inalmost-linear time. The running time of our algorithms is significantly betterthan previous algorithms that require quadratic time.  A key idea in our embedding is the construction of an (exact) emulator fortree metrics with treewidth $O(\log\log n)$ and hop-diameter $O(\log \log n)$.This result may be of independent interest.

Low Treewidth Embeddings of Planar and Minor-Free Metrics