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

Math @ Duke



Publications [#313246] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Fox, K; Nath, A; Sidiropoulos, A; Wang, Y, Computing the Gromov-Hausdorff distance for metric trees, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9472 (January, 2015), pp. 529-540, ISSN 0302-9743 [doi]
    (last updated on 2018/10/14)

    © Springer-Verlag Berlin Heidelberg 2015. 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 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, √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(√ n)-approximation algorithm.
ph: 919.660.2800
fax: 919.660.2821

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