Approximating a finite metric by a small number of tree metrics

Bartal [4, 5] gave a randomized polynomial time algorithm that given anp n point metric G, constructs a tree T such that the expected stretch (distortion) of any edge is at most O(log n log log n). His result has found several applications and in particular has resulted in approximation algorithms for many graph optimization problems. However approximation algorithms based on his result are inherently randomized. In this paper we derandomize the use of Bartal's algorithm in the design of approximation algorithms. We give an efficient polynomial time algorithm that given a finite n point metric G, constructs O(n log n) trees and a probability distribution mu on them such that the expected stretch of any edge of G in a tree chosen according to mu is at most O(log n log log n). Our result establishes that finite metrics can be probabilistically approximated by a small number of tree metrics. We obtain the first deterministic approximation algorithms for boy-at-bulk network design [2] and vehicle routing [7]; in addition we subsume results from our earlier work [8] on derandomization. Our main result is obtained by a novel view of probabilistic approximation of metric spaces as a deterministic optimization problem via linear programming. This view also provides a new proof of the result in [5] that might be easier to generalize. We also show that graphs induced by points in R-p(d) (dimensional real normed space equipped with the L-p norm) can be O(f(d, p) . log n)-probabilistically approximated by tree metrics where f(d,p) = d(1/p) for 1 less than or equal to p less than or equal to 2 and f(d,p) = d(1-1/p) for 2 less than or equal to p. We use an improved graph partitioning algorithm for normed spaces that obliviously partitions the space into clusters of diameter at most D such that the probability of two points u and v falling in different clusters is at most O(f(d, p) . parallel to u - v parallel to(p)/D) We also show that our clustering is optimal for all p by giving matching lower bounds.