Euclidean distortion and the sparsest cut

DOI10.1145/1060590.1060673zbMath1192.68870OpenAlexW2167061810MaRDI QIDQ3581404

Sanjeev Arora, James R. Lee, Assaf Naor

Publication date: 16 August 2010

Published in: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1060590.1060673

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (14)

A note on multiflows and treewidth ⋮ Approximation algorithms for the weighted \(t\)-uniform sparsest cut and some other graph partitioning problems ⋮ An improved approximation ratio for the minimum linear arrangement problem ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ \(\ell ^2_2\) spreading metrics for vertex ordering problems ⋮ Unbalanced graph partitioning ⋮ On the advantage of overlapping clusters for minimizing conductance ⋮ Advances in metric embedding theory ⋮ Cut problems in graphs with a budget constraint ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs ⋮ Ramsey partitions and proximity data structures ⋮ On Khot’s unique games conjecture ⋮ Unnamed Item

This page was built for publication: Euclidean distortion and the sparsest cut