Bicriteria approximation for minimum dilation graph augmentation
<|reference_start|>Bicriteria approximation for minimum dilation graph augmentation: 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\H{o}s girth conjecture.<|reference_end|>
@article{buchin2024bicriteria,
    title={Bicriteria approximation for minimum dilation graph augmentation},
    author={Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Sampson Wong},
    journal={arXiv preprint arXiv:2407.04614},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.04614},
    primaryClass={cs.CG}
}