Reality Distortion: Exact and Approximate Algorithms for Embedding into the Line

We describe algorithms for the problem of minimum distortion embeddings of finite metric spaces into the real line (or a finite subset of the line). The time complexities of our algorithms are parametrized by the values of the minimum distortion, δ, and the spread, Δ, of the point set we are embedding. We consider the problem of finding the minimum distortion bijection between two finite subsets of IR. This problem was known to have an exact polynomial time solution when δ is below a specific small constant, and hard to approximate within a factor of δ^1-E, when δ is polynomially large. Let D be the largest adjacent pair distance, a value potentially much smaller than Δ. Then we provide a δ^O(δ2log2D)nO⁽¹⁾ time exact algorithm for this problem, which in particular yields a quasipolynomial running time for constant δ, and polynomial D. For the more general problem of embedding any finite metric space (X, dX) into a finite subset of the line, Y , we provide a Δ^O(δ2)(mn)^O(1) time O(1)-approximation algorithm (where X = n and Y = m), which runs in polynomial time provided δ is a constant and Δ is polynomial. This in turn allows us to get a Δ^O(δ2)(n)O⁽¹⁾ time O(1)-approximation algorithm for embedding (X, dX) into the continuous real line.