Computing the Gromov-Hausdorff Distance for Metric Trees

Pankaj K. Agarwal, Kyle Fox, Abhinandan Nath, Anastasios Sidiropoulos, Yusu Wang

Abstract

The Gromov-Hausdorff (GH) distance is a natural way to measure distance between two metric spaces. We prove that it is NP-hard to approximate the GH distance better than a factor of 3 for geodesic metrics on a pair of trees. We complement this result by providing a polynomial time O(min n, √rn)-approximation algorithm for computing the GH distance between a pair of metric trees, where r is the ratio of the longest edge length in both trees to the shortest edge length. For metric trees with unit length edges, this yields an O(√ n)-approximation algorithm1.
BibTeX
@article{agarwal2015computing,
  author = {Pankaj K. Agarwal and Kyle Fox and Abhinandan Nath and Anastasios Sidiropoulos and Yusu Wang},
  title = {{Computing the Gromov-Hausdorff Distance for Metric Trees}},
  journal = {ACM Trans. Algorithms},
  year = {2015},
  doi = {10.1145/3185466},
}
Figure