Bypassing the embedding: algorithms for low dimensional metrics

  • Kunal Talwar

STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing |

Published by Association for Computing Machinery, Inc.

The doubling dimension of a metric is the smallest k such that any ball of radius 2r can be covered using 2k balls of radius r. This concept for abstract metrics has been proposed as a natural analog to the dimension of a Euclidean space. If we could embed metrics with low doubling dimension into low dimensional Euclidean spaces, they would inherit several algorithmic and structural properties of the Euclidean spaces. Unfortunately however, such a restriction on dimension does not suffice to guarantee embeddibility in a normed space. In this paper we explore the option of bypassing the embedding. In particular we show the following for low dimensional metrics:
• Quasi-polynomial time (1+)-approximation algorithm for various optimization problems such as TSP, k-median and facility location.
• (1+)-approximate distance labeling scheme with optimal label length.
• (1+)-stretch polylogarithmic storage routing scheme.