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

The multi-commodity flow-cut gap is a fundamental parameter that affects theperformance of several divide \& conquer algorithms, and has been extensivelystudied for various classes of undirected graphs. It has been shown by Linial,London and Rabinovich and by Aumann and Rabani that for general $n$-vertexgraphs it is bounded by $O(\log n)$ and the Gupta-Newman-Rabinovich-Sinclairconjecture asserts that it is $O(1)$ for any family of graphs that excludessome fixed minor.  We show that the multicommodity flow-cut gap on \emph{directed} planar graphsis $O(\log^3 n)$. This is the first \emph{sub-polynomial} bound for any familyof directed graphs of super-constant treewidth. We remark that for generaldirected graphs, it has been shown by Chuzhoy and Khanna that the gap is$\widetilde{\Omega}(n^{1/7})$, even for directed acyclic graphs.  As a direct consequence of our result, we also obtain the firstpolynomial-time polylogarithmic-approximation algorithms for the DirectedNon-Bipartite Sparsest-Cut, and the Directed Multicut problems for directedplanar graphs, which extends the long-standing result for undirectd planargraphs by Rao (with a slightly weaker bound).  At the heart of our result we investigate low-distortion quasimetricembeddings into \emph{directed} $\ell_1$. More precisely, we construct$O(\log^2 n)$-Lipschitz quasipartitions for the shortest-path quasimetricspaces of planar digraphs, which generalize the notion of Lipschitz partitionsfrom the theory of metric embeddings. This construction combines ideas from thetheory of bi-Lipschitz embeddings, with tools form data structures on directedplanar graphs.

Embeddings of Planar Quasimetrics into Directed \ell_1$ and Polylogarithmic Approximation for Directed Sparsest-Cut