Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces

Timothy Carpenter, Fedor V. Fomin, Daniel Lokshtanov +2

We study the problem of finding a minimum-distortion embedding of the shortest path metric of an unweighted graph into a "simpler" metric $X$. Computing such an embedding (exactly…