2024/07/05 by Buchin, Kevin, Buchin, Maike, Gudmundsson, Joachim +1
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2407.04614
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 √[r]2 k1/r,2r)-bicriteria approximation that runs in O(n3 log n) time, for all r ≥ 1. In other words, if t^* is the minimum dilation after adding any k edges to a graph, then our algorithm adds O(k1+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.