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:
URL: https://illinois.zoom.us/j/85236768481?pwd=RndkQzd2Vk5WMDNTdC9MQWZUemVjdz09
Meeting ID: 852 3676 8481
Password: theorycs
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.
