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

Ken-ichi Kawarabayashi, Anastasios Sidiropoulos

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 class…