Deshpande, Amit ;
Harsha, Prahladh ;
Venkat, Rakesh
Embedding Approximately LowDimensional l_2^2 Metrics into l_1
Abstract
Goemans showed that any n points x_1,..., x_n in ddimensions satisfying l_2^2 triangle inequalities can be embedded into l_{1}, with worstcase distortion at most sqrt{d}. We consider an extension of this theorem to the case when the points are approximately lowdimensional as opposed to exactly lowdimensional, and prove the following analogous theorem, albeit with average distortion guarantees: There exists an l_{2}^{2}tol_{1} embedding with average distortion at most the stable rank, sr(M), of the matrix M consisting of columns {x_ix_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 thresholdrank 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}.
BibTeX  Entry
@InProceedings{deshpande_et_al:LIPIcs:2016:6845,
author = {Amit Deshpande and Prahladh Harsha and Rakesh Venkat},
title = {{Embedding Approximately LowDimensional l_2^2 Metrics into l_1}},
booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
pages = {10:110:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770279},
ISSN = {18688969},
year = {2016},
volume = {65},
editor = {Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6845},
URN = {urn:nbn:de:0030drops68456},
doi = {10.4230/LIPIcs.FSTTCS.2016.10},
annote = {Keywords: Metric Embeddings, Sparsest Cut, Negative type metrics, Approximation Algorithms}
}
10.12.2016
Keywords: 

Metric Embeddings, Sparsest Cut, Negative type metrics, Approximation Algorithms 
Seminar: 

36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Issue date: 

2016 
Date of publication: 

10.12.2016 