Abstract
We consider the question of embedding metrics induced by trees into Euclidean spaces with a restricted number of dimensions. We show that any weighted tree T with n(T) vertices and l(T) leaves can be embedded into d-dimensional Euclidean space with O(l(T)1/(d-1)) distortion. Further, we exhibit an embedding with almost the same distortion which can be computed efficiently. This distortion substantially improves the previous best upper bound of O(n(T)2/d) and almost matches the best known lower bound of Ω(l(T)1/d).
Original language | English (US) |
---|---|
Pages (from-to) | 694-700 |
Number of pages | 7 |
Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |
DOIs | |
State | Published - 1999 |
Event | Proceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA Duration: May 1 1999 → May 4 1999 |
ASJC Scopus subject areas
- Software