The Gromov-Hausdorff distance between ultrametric spaces

Image
Topology, Geometry and Data Seminar
October 12, 2021
4:00PM - 5:00PM
Location
Zoom

Date Range
Add to Calendar 2021-10-12 16:00:00 2021-10-12 17:00:00 The Gromov-Hausdorff distance between ultrametric spaces Title:  The Gromov-Hausdorff distance between ultrametric spaces Speaker:  Zhengchao Wan (OSU) Speaker's URL:  https://zhengchaow.github.io Abstract:  The Gromov-Hausdorff distance ($d_{\mathrm{GH}}$) is a natural distance between metric spaces. However, computing $d_{\mathrm{GH}}$ is NP-hard, even in the case of finite ultrametric spaces. We identify a one parameter family $\{d_{\mathrm{GH}, p}\}_{p\in[1,\infty]}$ of Gromov-Hausdorff type distances on the collection of ultrametric spaces such that $d_{\mathrm{GH}, 1} =d_{\mathrm{GH}}$. The extreme case when $p=\infty$, which we also denote by $u_{\mathrm{GH}}$, turns out to be an ultrametric on the collection of ultrametric spaces. We discuss various geometric and topological properties of $d_{\mathrm{GH}, p}$ as well as some of its structural results. These structural results in turn allow us to study the computational aspects of the distance. In particular, we establish that (1) $u_{\mathrm{GH}}$ is computationally tractable and (2) when $p<\infty$, although $d_{\mathrm{GH}, p}$ is NP-hard to compute, we identify a fixed-parameter tractable algorithm for computing the exact value of $d_{\mathrm{GH}, p}$ between finite ultrametric spaces. Zoom Department of Mathematics math@osu.edu America/New_York public
Description

Title:  The Gromov-Hausdorff distance between ultrametric spaces

Speaker:  Zhengchao Wan (OSU)

Speaker's URL:  https://zhengchaow.github.io

Abstract:  The Gromov-Hausdorff distance ($d_{\mathrm{GH}}$) is a natural distance between metric spaces. However, computing $d_{\mathrm{GH}}$ is NP-hard, even in the case of finite ultrametric spaces. We identify a one parameter family $\{d_{\mathrm{GH}, p}\}_{p\in[1,\infty]}$ of Gromov-Hausdorff type distances on the collection of ultrametric spaces such that $d_{\mathrm{GH}, 1} =d_{\mathrm{GH}}$. The extreme case when $p=\infty$, which we also denote by $u_{\mathrm{GH}}$, turns out to be an ultrametric on the collection of ultrametric spaces. We discuss various geometric and topological properties of $d_{\mathrm{GH}, p}$ as well as some of its structural results. These structural results in turn allow us to study the computational aspects of the distance. In particular, we establish that (1) $u_{\mathrm{GH}}$ is computationally tractable and (2) when $p<\infty$, although $d_{\mathrm{GH}, p}$ is NP-hard to compute, we identify a fixed-parameter tractable algorithm for computing the exact value of $d_{\mathrm{GH}, p}$ between finite ultrametric spaces.

Events Filters: