Inapproximability for metric embeddings into R^d

Jiri Matousek, Anastasios Sidiropoulos

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 fixed (and small). For d=1, it was known th…