Bicriteria approximation for minimum dilation graph augmentation
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_ | 1866913418654515200 |
|---|---|
| author | Buchin, Kevin Buchin, Maike Gudmundsson, Joachim Wong, Sampson |
| author_facet | Buchin, Kevin Buchin, Maike Gudmundsson, Joachim Wong, Sampson |
| contents | Spanner constructions focus on the initial design of the network. However, networks tend to improve over time. In this paper, we focus on the improvement step. Given a graph and a budget $k$, which $k$ edges do we add to the graph to minimise its dilation? Gudmundsson and Wong [TALG'22] provided the first positive result for this problem, but their approximation factor is linear in $k$.
Our main result is a $(2 \sqrt[r]{2} \ k^{1/r},2r)$-bicriteria approximation that runs in $O(n^3 \log n)$ time, for all $r \geq 1$. In other words, if $t^*$ is the minimum dilation after adding any $k$ edges to a graph, then our algorithm adds $O(k^{1+1/r})$ edges to the graph to obtain a dilation of $2rt^*$. Moreover, our analysis of the algorithm is tight under the Erdős girth conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_04614 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Bicriteria approximation for minimum dilation graph augmentation Buchin, Kevin Buchin, Maike Gudmundsson, Joachim Wong, Sampson Computational Geometry Spanner constructions focus on the initial design of the network. However, networks tend to improve over time. In this paper, we focus on the improvement step. Given a graph and a budget $k$, which $k$ edges do we add to the graph to minimise its dilation? Gudmundsson and Wong [TALG'22] provided the first positive result for this problem, but their approximation factor is linear in $k$. Our main result is a $(2 \sqrt[r]{2} \ k^{1/r},2r)$-bicriteria approximation that runs in $O(n^3 \log n)$ time, for all $r \geq 1$. In other words, if $t^*$ is the minimum dilation after adding any $k$ edges to a graph, then our algorithm adds $O(k^{1+1/r})$ edges to the graph to obtain a dilation of $2rt^*$. Moreover, our analysis of the algorithm is tight under the Erdős girth conjecture. |
| title | Bicriteria approximation for minimum dilation graph augmentation |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2407.04614 |