Approximation algorithms for minimizing average distortion

Kedar Dhamdhere, Anupam Gupta, R. Ravi

Research output: Contribution to journalArticlepeer-review


This paper considers embeddings f of arbitrary finite metrics into the line metric ℛ so that none of the distances is shrunk by the embedding f; the quantity of interest is the factor by which the average distance in the metric is stretched. We call this quantity the average distortion of the non-contracting map f. We prove that finding the best embedding of even a tree metric into a line metric to minimize the average distortion is NP-hard, and hence focus on approximating the average distortion of the best possible embedding for the given input metric. We give a constant-factor approximation for the problem of embedding general metrics into the line metric. For the case of n-point tree metrics, we provide a quasi-polynomial time approximation scheme which outputs an embedding with distortion at most (1 + ε) times the optimum in time nO(log n/ε2). Finally, when the average distortion is measured only over the endpoints of the edges of an input tree metric, we show how to exploit the structure of tree metrics to give an exact solution in polynomial time.

Original languageEnglish (US)
Pages (from-to)93-111
Number of pages19
JournalTheory of Computing Systems
Issue number1
StatePublished - Feb 2006

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics


Dive into the research topics of 'Approximation algorithms for minimizing average distortion'. Together they form a unique fingerprint.

Cite this