文章基本信息

标题：Embedding Approximately Low-Dimensional l_2^2 Metrics into l_1
本地全文：下载
作者：Amit Deshpande ; Prahladh Harsha ; Rakesh Venkat 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：65
页码：10:1-10:13
DOI：10.4230/LIPIcs.FSTTCS.2016.10
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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
关键词：Metric Embeddings; Sparsest Cut; Negative type metrics; Approximation Algorithms