Computing the Gromov-Hausdorff Distance for Metric Trees
Computing the Gromov-Hausdorff Distance for Metric Trees
复制标题
计算度量树的 Gromov-Hausdorff 距离
DOI：
10.1145/3185466
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Yusu Wang
中科院分区：
文献类型：
--
作者：
P. Agarwal;K. Fox;Abhinandan Nath;Anastasios Sidiropoulos;Yusu Wang
Gromov-Hausdorff（GH）距离是度量两个度量空间之间距离的一种自然方法。我们证明了这是NP-困难的近似GH距离优于3倍的测地线度量对树。我们补充这一结果，提供了一个多项式时间O（min n，n）-近似算法计算GH之间的距离对度量树，其中r是最长的边长度在两棵树的最短边长度的比率。对于具有单位长度边的度量树，这产生了O（n）-近似算法1。
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.