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.
|Original language||English (US)|
|Number of pages||10|
|Journal||Annual Symposium on Foundations of Computer Science - Proceedings|
|State||Published - 1998|
ASJC Scopus subject areas
- Hardware and Architecture