Dynamic Metric Embedding into $\ell_p$ Space
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910564942348288 |
|---|---|
| author | Banihashem, Kiarash Hajiaghayi, MohammadTaghi Kowalski, Dariusz R. Olkowski, Jan Springer, Max |
| author_facet | Banihashem, Kiarash Hajiaghayi, MohammadTaghi Kowalski, Dariusz R. Olkowski, Jan Springer, Max |
| contents | We give the first non-trivial decremental dynamic embedding of a weighted, undirected graph $G$ into $\ell_p$ space. Given a weighted graph $G$ undergoing a sequence of edge weight increases, the goal of this problem is to maintain a (randomized) mapping $ϕ: (G,d) \to (X,\ell_p)$ from the set of vertices of the graph to the $\ell_p$ space such that for every pair of vertices $u$ and $v$, the expected distance between $ϕ(u)$ and $ϕ(v)$ in the $\ell_p$ metric is within a small multiplicative factor, referred to as the \emph{distortion}, of their distance in $G$. Our main result is a dynamic algorithm with expected distortion $O(\log^3 n)$ and total update time $O\left((m^{1+o(1)} \log^2 W + Q \log n)\log(nW) \right)$, where $W$ is the maximum weight of the edges, $Q$ is the total number of updates and $n, m$ denote the number of vertices and edges in $G$ respectively. This is the first result of its kind, extending the seminal result of Bourgain to the growing field of dynamic algorithms. Moreover, we demonstrate that in the fully dynamic regime, where we tolerate edge insertions as well as deletions, no algorithm can explicitly maintain an embedding into $\ell_p$ space that has a low distortion with high probability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_17210 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Dynamic Metric Embedding into $\ell_p$ Space Banihashem, Kiarash Hajiaghayi, MohammadTaghi Kowalski, Dariusz R. Olkowski, Jan Springer, Max Data Structures and Algorithms We give the first non-trivial decremental dynamic embedding of a weighted, undirected graph $G$ into $\ell_p$ space. Given a weighted graph $G$ undergoing a sequence of edge weight increases, the goal of this problem is to maintain a (randomized) mapping $ϕ: (G,d) \to (X,\ell_p)$ from the set of vertices of the graph to the $\ell_p$ space such that for every pair of vertices $u$ and $v$, the expected distance between $ϕ(u)$ and $ϕ(v)$ in the $\ell_p$ metric is within a small multiplicative factor, referred to as the \emph{distortion}, of their distance in $G$. Our main result is a dynamic algorithm with expected distortion $O(\log^3 n)$ and total update time $O\left((m^{1+o(1)} \log^2 W + Q \log n)\log(nW) \right)$, where $W$ is the maximum weight of the edges, $Q$ is the total number of updates and $n, m$ denote the number of vertices and edges in $G$ respectively. This is the first result of its kind, extending the seminal result of Bourgain to the growing field of dynamic algorithms. Moreover, we demonstrate that in the fully dynamic regime, where we tolerate edge insertions as well as deletions, no algorithm can explicitly maintain an embedding into $\ell_p$ space that has a low distortion with high probability. |
| title | Dynamic Metric Embedding into $\ell_p$ Space |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2406.17210 |