License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2016.10
URN: urn:nbn:de:0030-drops-68456
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6845/
Deshpande, Amit ;
Harsha, Prahladh ;
Venkat, Rakesh
Embedding Approximately Low-Dimensional l_2^2 Metrics into l_1
Abstract
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}.
BibTeX - Entry
@InProceedings{deshpande_et_al:LIPIcs:2016:6845,
author = {Amit Deshpande and Prahladh Harsha and Rakesh Venkat},
title = {{Embedding Approximately Low-Dimensional 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:1--10:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-027-9},
ISSN = {1868-8969},
year = {2016},
volume = {65},
editor = {Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6845},
URN = {urn:nbn:de:0030-drops-68456},
doi = {10.4230/LIPIcs.FSTTCS.2016.10},
annote = {Keywords: Metric Embeddings, Sparsest Cut, Negative type metrics, Approximation Algorithms}
}
|
Keywords: |
|
Metric Embeddings, Sparsest Cut, Negative type metrics, Approximation Algorithms |
|
Collection: |
|
36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
10.12.2016 |
