Computing the Gromov-Hausdorff Distance for Metric Trees

Pankaj K. Agarwal, Kyle Fox, Abhinandan Nath +2

The Gromov-Hausdorff (GH) distance is a natural way to measure distance between two metric spaces. We prove that it is $\mathrm{NP}$-hard to approximate the Gromov-Hausdorff distan…