Kenyon et al. (STOC 04) compute the distortion between one-dimensional finite point sets when the distortion is small; Papadimitriou
and Safra (SODA 05) show that the problem is NP-hard to approximate within a factor of 3, albeit in 3 dimensions. We solve
an open problem in these two papers by demonstrating that, when the distortion is large, it is hard to approximate within
large factors, even for 1-dimensional point sets. We also introduce additive distortion, and show that it can be easily approximated
within a factor of two.
Work partially supported by European Commission – Fet Open project DELIS IST-001907 Dynamically Evolving Large Scale Information
Systems.