## Abstract

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) |
---|---|

Pages (from-to) | 379-388 |

Number of pages | 10 |

Journal | Annual Symposium on Foundations of Computer Science - Proceedings |

State | Published - 1998 |

Externally published | Yes |

Event | Proceedings of the 1998 39th Annual Symposium on Foundations of Computer Science - Palo Alto, CA, USA Duration: Nov 8 1998 → Nov 11 1998 |

## ASJC Scopus subject areas

- Hardware and Architecture