Low dimensional embeddings of ultrametrics. (Q1422397): Difference between revisions

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.