TY - GEN

T1 - A quasipolynomial (2 + ?)-approximation for planar sparsest cut

AU - Cohen-Addad, Vincent

AU - Gupta, Anupam

AU - Klein, Philip N.

AU - Li, Jason

N1 - Publisher Copyright:
© 2021 ACM.

PY - 2021/6/15

Y1 - 2021/6/15

N2 - 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. We consider the problem for planar graphs, and give a (2+)-approximation algorithm that runs in quasipolynomial time. Our approach defines a new structural decomposition of an optimal solution using a "patching"primitive. We combine this decomposition with a Sherali-Adams-style linear programming relaxation of the problem, which we then round. This should be compared with the polynomial-time approximation algorithm of Rao (1999), which uses the metric linear programming relaxation and ?1-embeddings, and achieves an O(?logn)-approximation in polynomial time.

AB - 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. We consider the problem for planar graphs, and give a (2+)-approximation algorithm that runs in quasipolynomial time. Our approach defines a new structural decomposition of an optimal solution using a "patching"primitive. We combine this decomposition with a Sherali-Adams-style linear programming relaxation of the problem, which we then round. This should be compared with the polynomial-time approximation algorithm of Rao (1999), which uses the metric linear programming relaxation and ?1-embeddings, and achieves an O(?logn)-approximation in polynomial time.

KW - Approximation algorithms

KW - Graph Partitioning

KW - LP Rounding

KW - Non-Uniform Sparsest Cut

KW - Planar Graphs

UR - http://www.scopus.com/inward/record.url?scp=85108151675&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85108151675&partnerID=8YFLogxK

U2 - 10.1145/3406325.3451103

DO - 10.1145/3406325.3451103

M3 - Conference contribution

AN - SCOPUS:85108151675

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1056

EP - 1069

BT - STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

A2 - Khuller, Samir

A2 - Williams, Virginia Vassilevska

PB - Association for Computing Machinery

T2 - 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021

Y2 - 21 June 2021 through 25 June 2021

ER -