  The Gromov-Hausdorff distance provides a metric on the set of isometry
classes of compact metric spaces. Unfortunately, computing this metric directly
is believed to be computationally intractable. Motivated by applications in
shape matching and point-cloud comparison, we study a semidefinite programming
relaxation of the Gromov-Hausdorff metric. This relaxation can be computed in
polynomial time, and somewhat surprisingly is itself a pseudometric. We
describe the induced topology on the set of compact metric spaces. Finally, we
demonstrate the numerical performance of various algorithms for computing the
relaxed distance and apply these algorithms to several relevant data sets. In
particular we propose a greedy algorithm for finding the best correspondence
between finite metric spaces that can handle hundreds of points.
