Publication at Faculty of Mathematics and Physics |
2010
Abstract
We consider the problem of computing the smallest possible distortion for embedding of a given $n$-point metric space into $\R^d$, where $d$is \emph{fixed} (and small). For $d=1$, it was known that approximating the minimum distortion with a factor better than roughly $n^{1/12}$ is NP-hard.