Math @ Duke

Publications [#313246] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Fox, K; Nath, A; Sidiropoulos, A; Wang, Y, Computing the GromovHausdorff 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. 529540, ISSN 03029743 [doi]
(last updated on 2018/10/14)
Abstract: © SpringerVerlag Berlin Heidelberg 2015. The GromovHausdorff distance is a natural way to measure distance between two metric spaces. We give the first proof of hardness and first nontrivial approximation algorithm for computing the GromovHausdorff distance for geodesic metrics in trees. Specifically, we prove it is NPhard to approximate the GromovHausdorff 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

