Improving the average dilation of a metric graph by adding edges
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913876760592384 |
|---|---|
| author | Har-Peled, Sariel Robson, Eliot W. |
| author_facet | Har-Peled, Sariel Robson, Eliot W. |
| contents | For a graph $G$ spanning a metric space, the dilation of a pair of points is the ratio of their distance in the shortest path graph metric to their distance in the metric space. Given a graph $G$ and a budget $k$, a classic problem is to augment $G$ with $k$ additional edges to reduce the maximum dilation.
In this note, we consider a variant of this problem where the goal is to reduce the average dilation for pairs of points in $G$. We provide an $O(k)$ approximation algorithm for this problem, matching the approximation ratio given by prior work for the maximum dilation variant. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_04246 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improving the average dilation of a metric graph by adding edges Har-Peled, Sariel Robson, Eliot W. Computational Geometry For a graph $G$ spanning a metric space, the dilation of a pair of points is the ratio of their distance in the shortest path graph metric to their distance in the metric space. Given a graph $G$ and a budget $k$, a classic problem is to augment $G$ with $k$ additional edges to reduce the maximum dilation. In this note, we consider a variant of this problem where the goal is to reduce the average dilation for pairs of points in $G$. We provide an $O(k)$ approximation algorithm for this problem, matching the approximation ratio given by prior work for the maximum dilation variant. |
| title | Improving the average dilation of a metric graph by adding edges |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2506.04246 |