Low dimensional embeddings of ultrametrics.
type: Item
instance of: scholarly article
title: Low dimensional embeddings of ultrametrics.
zbMATH Open document ID: 1042.54020
author: Yair Bartal
author: Manor Mendel
author: Assaf Naor
author: Nathan Linial
published in: European Journal of Combinatorics
publication date: 2004-02-14T00:00:00Z
review text: In the recent years, low-distortion embeddings of finite metric spaces into normed linear spaces became recognized as a very powerful toolkit for designing efficient algorithms. See \textit{J.~Matousek} [Chapter 15 in: Lectures on discrete geometry, Spinger, New York (2002; Zbl 0999.52006)] for an introduction to the area. An \textit{ultrametric} is a metric space satisfying the condition \[ d(x,z)\leq\max\{d(x,y),~d(y,z)\}~\forall x,y,z. \] It is well known that a finite ultrametric is isometric to a subset of \(\ell_2\) and, hence, to a subset of \(\ell_p\). The main result of the paper is an estimate for \(m\) such that there exist low-distortion embeddings of \(n\)-element ultrametrics into \(\ell_p^m\). It is shown that \(m=O(\log n)\). The result is stated and proved in a more general context of hierarchically well-separated trees, introduced by \textit{Y.~Bartal} [Probabilistic approximation of metric spaces and its algorithmic applications, 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), 184--193, IEEE Comput. Soc. Press, Los Alamitos, CA (1996)]. The result is applied to metric Ramsey-type problems.
Mathematics Subject Classification ID: 54E35
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 46B07
Mathematics Subject Classification ID: 54C25
zbMATH DE Number: 2041880
zbMATH Keywords: ultrametric
zbMATH Keywords: distortion of an embedding
zbMATH Keywords: Banach space
zbMATH Keywords: metric Ramsey theory
reviewed by: Mikhail Ostrovskii
MaRDI profile type: Publication
full work available at URL: j.ejc.2003.08.003
OpenAlex ID: W2016332796
cites work: A Review of Hierarchical Classification
cites work: Q4542533
cites work: On metric Ramsey-type phenomena
cites work: A tight bound on approximating arbitrary metrics by tree metrics
cites work: Isometric embedding of ultrametric (non-Archimedean) spaces in Hilbert space and Lebesgue space
cites work: Extensions of Lipschitz mappings into a Hilbert space
cites work: The dimension of almost spherical sections of convex bodies
DOI: 10.1016/J.EJC.2003.08.003
Recommended article: On metric Ramsey-type phenomena
Recommended article: Limitations to Fréchet's metric embedding method
Recommended article: Multiembedding of Metric Spaces
Recommended article: Fat polygonal partitions with applications to visualization and embeddings
Recommended article: Q4542534
Recommended article: Embedding tree metrics into low dimensional Euclidean spaces
Recommended article: Q2934632
Recommended article: Q5501324
Recommended article: Q4633900
Recommended article: Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion
description: scientific article; zbMATH DE number 2041880