We show that every n-point metric of negative type (in particular, every n-point subset of L 1) admits a Fréchet embedding into Euclidean space with distortion O(√log n · log log n), a result which is tight up to the O(log∈log∈n) factor, even for Euclidean metrics. This strengthens our recent work on the Euclidean distortion of metrics of negative into Euclidean space.
- Metric embeddings
- Sparsest cut problem
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics