2026-07-29T13:01:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21107 2024-09-23T09:13:16Z ddc:004 open_access

Bicriteria Approximation for Minimum Dilation Graph Augmentation Buchin, Kevin Buchin, Maike Gudmundsson, Joachim Wong, Sampson Greedy spanner 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 √[r]{2} k^{1/r},2r)-bicriteria approximation that runs in O(n³ 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(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kevin Buchin and Maike Buchin and Joachim Gudmundsson and Sampson Wong 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.36 urn:nbn:de:0030-drops-211079 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.36 eng https://creativecommons.org/licenses/by/4.0/legalcode