Approximating a finite metric by a small number of tree metrics

The use of Bartal's algorithm is derandomized in the design of approximation algorithms. The efficient polynomial time algorithm is given a finite n point metric G, where it constructs O(n log n) trees, and a probability distribution μ on them, such that the expected stretch of any edge of G in a tree chosen according to μ is at most O(log n log log n). The result establishes that finite metrics can be probabilistically approximated by a small number of tree metrics. The main result is obtained by a novel view of probabilistic approximation of metric spaces as a deterministic optimization problem via linear programming.