BARC talk by Sampson Wong

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.

Bio: Sampson Wong is a 3rd year PhD candidate, supervised by Joachim Gudmundsson at the University of Sydney. His interests are in Algorithms and Computational Geometry. He also likes tennis and solving high school geometry problems.