Bypassing the Embedding: Algorithms for low dimensional metrics.

Speaker: Kunal Talwar, MSR


The doubling dimension of a metric is the smallest $k$ such that any
ball of radius $2r$ in the metric can be covered using $2^k$ 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 this talk, we'll explore the option of bypassing the embedding for
several applications. We'll derive results analogous to Euclidean
spaces for low dimensional abstract metric spaces. In particular,
we'll show that low dimensional abstract spaces admit: quasipolynomial
time approximation scheme for various optimization problems including
the TSP; short approximate distance labels; compact approximate
shortest path routing schemes.