Low Distortion Maps in One Dimension

Abstract

Given as input two n-point metric spaces, the minimum distortion problem asks for a bijection between them with minimum distortion. This is an abstraction of certain geometric problems in shape and image matching, and is also a natural extension of graph isomorphism and bandwidth. Our focus is on algorithms that find an optimal (or near-optimal) bijection when the distortion is fairly small. We present a polynomial time algorithm that finds an optimal bijection between two line metrics, provided the distortion is at most 9.90... This relies on a characterazation of the best distortion achievable by a permutation in terms of leading eigenvalues. We also give a parameterized polynomial time algorithm that finds an optimal bijection between an arbitrary unweighted graph metric and a bounded-degree tree metric.

This is joint work with Sylvain Biehler, Yuval Rabani and Alistair Sinclair.