2015/12/14 by Amit Deshpande, Deshpande, Amit, Prahladh Harsha +3
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Mathematical Approximation and Integration #cs.DS
paper · pdf · doi:10.48550/arxiv.1512.04170
arxiv created 2015/12/14 · openalex publication_date 2015/12/14 · arxiv updated 2015/12/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Goemans showed that any n points x1, \dotsc xn in d-dimensions satisfying ℓ22 triangle inequalities can be embedded into ℓ1, with worst-case distortion at most √(d). We extend this to the case when the points are approximately low-dimensional, albeit with average distortion guarantees. More precisely, we give an ℓ22-to-ℓ1 embedding with average distortion at most the stable rank, sr(M), of the matrix M consisting of columns \xi-xj\i<j. Average distortion embedding suffices for applications such as the Sparsest Cut problem. Our embedding gives an approximation algorithm for the \sparsestcut problem on low threshold-rank graphs, where earlier work was inspired by Lasserre SDP hierarchy, and improves on a previous result of the first and third author [Deshpande and Venkat, In Proc. 17th APPROX, 2014]. Our ideas give a new perspective on ℓ22 metric, an alternate proof of Goemans' theorem, and a simpler proof for average distortion √(d). Furthermore, while the seminal result of Arora, Rao and Vazirani giving a O(√(log n)) guarantee for Uniform Sparsest Cut can be seen to imply Goemans' theorem with average distortion, our work opens up the possibility of proving such a result directly via a Goemans'-like theorem.