Back to Listing

NCSA staff who would like to submit an item for the calendar can email

Theory Seminar: Anastasios (Taso) Sidiropoulos, "Embeddings of Planar Quasimetrics into Directed L_1 and Polylogarithmic Approximation for Directed Sparsest-Cut"

Event Type
Chandra Chekuri
wifi event
Oct 25, 2021   10:00 am  
Originating Calendar
Computer Science Speakers Calendar

The seminar will be online via zoom and will be projected in Siebel 3124 (masks mandatory) for those who want to attend in person.


The zoom details are:


Meeting ID: 852 3676 8481



The details of the talk are:


Title :  Embeddings of Planar Quasimetrics into Directed L_1 and Polylogarithmic Approximation for Directed Sparsest-Cut

Abstract:  The multi-commodity flow-cut gap is a fundamental parameter that affects the performance of several divide \& conquer algorithms, and has been extensively studied for various classes of undirected graphs. It has been shown by [Linial, London and Rabinovich 1994] and by [Aumann and Rabani 1998] that for general n-vertex graphs it is bounded by O(log n) and the Gupta-Newman-Rabinovich-Sinclair conjecture asserts that it is O(1) for any family of graphs that excludes some fixed minor.

We show that the multicommodity flow-cut gap on \emph{directed} planar graphs is  O(log^3 n). This is the first \emph{sub-polynomial} bound for any family of directed graphs of super-constant treewidth. We remark that for general directed graphs, it has been shown by [Chuzhoy and Khanna 2009] that the gap is Omega(n^(1/7)), even for directed acyclic graphs.

As a direct consequence of our result, we also obtain the first polynomial-time polylogarithmic-approximation algorithms for the Directed Non-Bipartite Sparsest-Cut, and the Directed Multicut problems for directed planar graphs, which extends the long-standing result for undirected planar graphs by [Rao 99] (with a slightly weaker bound).

At the heart of our result we investigate low-distortion quasimetric embeddings into \emph{directed} $\ell_1$.
More precisely, we construct O(log^2 n)-Lipschitz quasipartitions for the shortest-path quasimetric spaces of planar digraphs, which generalize the notion of Lipschitz partitions from the theory of metric embeddings. This construction combines ideas from the theory of bi-Lipschitz embeddings, with tools form data structures on directed planar graphs.


Joint work with Ken-ichi Kawarabayashi, to appear in FOCS 2021.

link for robots only