TY - CHAP

T1 - Metric structures in L1

T2 - Dimension, snowflakes, and average distortion

AU - Lee, James R.

AU - Mendel, Manor

AU - Naor, Assaf

PY - 2004

Y1 - 2004

N2 - We study the metric properties of finite subsets of L1. The analysis of such metrics is central to a number of important algorithmic problems involving the cut structure of weighted graphs, including the Sparsest Cut Problem, one of the most compelling open problems in the field of approximation. Additionally, many open questions in geometric non-linear functional analysis involve the properties of finite subsets of L1. We present some new observations concerning the relation of L1 to dimension, topology, and Euclidean distortion. We show that every n-point subset of L1 embeds into L2 with average distortion O(√log n), yielding the first evidence that the conjectured worst-case bound of O(√log n) is valid. We also address the issue of dimension reduction in Lp for p ∈(1,2). We resolve a question left open in [1] about the impossibility of linear dimension reduction in the above cases, and we show that the example of [2,3] cannot be used to prove a lower bound for the non-linear case. This is accomplished by exhibiting constant-distortion embeddings of snowflaked planar metrics into Euclidean space.

AB - We study the metric properties of finite subsets of L1. The analysis of such metrics is central to a number of important algorithmic problems involving the cut structure of weighted graphs, including the Sparsest Cut Problem, one of the most compelling open problems in the field of approximation. Additionally, many open questions in geometric non-linear functional analysis involve the properties of finite subsets of L1. We present some new observations concerning the relation of L1 to dimension, topology, and Euclidean distortion. We show that every n-point subset of L1 embeds into L2 with average distortion O(√log n), yielding the first evidence that the conjectured worst-case bound of O(√log n) is valid. We also address the issue of dimension reduction in Lp for p ∈(1,2). We resolve a question left open in [1] about the impossibility of linear dimension reduction in the above cases, and we show that the example of [2,3] cannot be used to prove a lower bound for the non-linear case. This is accomplished by exhibiting constant-distortion embeddings of snowflaked planar metrics into Euclidean space.

UR - http://www.scopus.com/inward/record.url?scp=35048840167&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35048840167&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-24698-5_44

DO - 10.1007/978-3-540-24698-5_44

M3 - Chapter

AN - SCOPUS:35048840167

SN - 3540212582

SN - 9783540212584

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 401

EP - 412

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Farach-Colton, Martin

PB - Springer Verlag

ER -