In computer science, when dealing with difficult problems involving graphs and their associated metrics we resort to using two techniques. The first is to solve the problem on a simple subcase, in particular, on tree. The second is to devise an approximation algorithm, often one that is based on divide and conquer. In a 1996 paper [2], Bartal defined a class of tree metrics and devised methods for embedding metrics into such metrics that unified these two approaches for a broad set of problems. In particular, he defined a k hierarchically well separated tree (k-HST) which arises from a rooted weighted tree where the weights decrease by exactly a factor of k with increasing depth in the tree. Notice that such a weighted tree gives rise to a metric on the points in the tree. He further gave a randomized algorithm to embed any finite metric into such a tree metric where each pair in the original metric is at least as far in the tree metric and on expectation the distance between the pair does not stretch by more than an O(log{sup}2n) factor. He gave numerous applications to designing on-line algorithms using this embedding using on-line algorithms for trees. Approximation algorithms for various problems were quick to follow.
展开▼
