A quasipolynomial (2 + ε )-approximation for planar sparsest cut
Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li · 2021
The (non-uniform) sparsest cut problem is the following graph-partitioning problem: given a “supply” graph, and demands on pairs of vertices, delete some subset of supply edges to minimize the ratio of the supply edges cut to the total demand of the pairs separated by this deletion. Despite much effort, there are only a handful of nontrivial classes of supply graphs for which constant-factor approximations are known.