|
Abstract : |
This paper is concerned with probabilistic approximation of metric spaces. In previous work we introduced the method of ecient approximation of metrics by more simple families of metrics in a probabilistic fashion. In particular we study probabilistic approximations of arbitrary metric spaces by \hierarchically wellseparated tree " metric spaces. This has proved as a useful technique for simplifying the solutions to various problems. In this paper we improve the result by proving an approximation factor of O(log n log log n) getting the gap to the lower bound within lower order factors. We also give a deterministic version of the result which gives a tree with low average distortion of distances. The results have applications in a variety of areas including approximation algorithms, on-line algorithms and distributed computation and hence we obtain new approximation bounds for these applications., |
