Approximating a finite metric by a small number of tree metrics

M. Charikar, Chandra Sekhar Chekuri, A. Goel, S. Guha, S. Plotkin

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)379-388
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - 1998
Externally publishedYes

    Fingerprint

ASJC Scopus subject areas

  • Hardware and Architecture

Cite this