Computing the Gromov-Hausdorff Distance for Metric Trees
Lists
Only you see this
Abstract
The Gromov-Hausdorff distance is a natural way to measure distance between two metric spaces. We give the first proof of hardness and first non-trivial approximation algorithm for computing the Gromov-Hausdorff distance for geodesic metrics in trees. Specifically, we prove it is $$\mathrm {NP}$$ -hard to approximate the Gromov-Hausdorff distance better than a factor of 3. We complement this result by providing a polynomial time $$O(\min \{n, \sqrt{rn}\})$$ -approximation algorithm 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(\sqrt{n})$$ -approximation algorithm.
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},
}