Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#337581] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Kyle, FOX; Nath, A; Sidiropoulos, A; Wang, Y, Computing the gromov-hausdorff distance for metric trees, Acm Transactions on Algorithms, vol. 14 no. 2 (June, 2018), pp. 1-20, Association for Computing Machinery (ACM) [doi]
    (last updated on 2023/06/02)

    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 algorithm.1

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320