2025/05/30 by Har-Peled, Sariel, Robson, Eliot W.
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2506.04246
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.