Improving the dilation of a metric graph by adding edges

Most of the literature on spanners focuses on building the graph from scratch. This paper instead focuses on adding edges to improve an existing graph. A major open problem in this field is: given a graph embedded in a metric space, and a budget of k edges, which k edges do we add to produce a minimum-dilation graph? The special case where k = 1 has been studied in the past, but no major breakthroughs have been made for k > 1. We provide the first positive result, an O(k)-approximation algorithm that runs in O(n 3 log n) time.