2026-07-21T11:11:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6845 2024-03-06T10:39:01Z ddc:004 open_access

Embedding Approximately Low-Dimensional l_2^2 Metrics into l_1 Deshpande, Amit Harsha, Prahladh Venkat, Rakesh Metric Embeddings Sparsest Cut Negative type metrics Approximation Algorithms Goemans showed that any n points x_1,..., x_n in d-dimensions satisfying l_2^2 triangle inequalities can be embedded into l_{1}, with worst-case distortion at most sqrt{d}. We consider an extension of this theorem to the case when the points are approximately low-dimensional as opposed to exactly low-dimensional, and prove the following analogous theorem, albeit with average distortion guarantees: There exists an l_{2}^{2}-to-l_{1} embedding with average distortion at most the stable rank, sr(M), of the matrix M consisting of columns {x_i-x_j}_{i<j}. Average distortion embedding suffices for applications such as the SPARSEST CUT problem. Our embedding gives an approximation algorithm for the SPARSEST CUT 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 l_{2}^{2} metric, an alternate proof of Goemans' theorem, and a simpler proof for average distortion sqrt{d}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amit Deshpande and Prahladh Harsha and Rakesh Venkat 2016 Is Part Of LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2016.10 urn:nbn:de:0030-drops-68456 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.10 eng https://creativecommons.org/licenses/by/3.0/legalcode