This project studies approximation algorithms in certain metric spaces, especially weighted planar graphs and low-dimensional Euclidean spaces, possibly with obstacles. Problems studied include light-weight spanner graphs for such metrics, separators with appropriate trade-offs between weight and connectivity, reductions between metric spaces, and algorithmic design principles such as dynamic programming and random sampling.
The main objective is the development of efficient approximation schemes for well-known optimization problems in these metrics; these problems include the Traveling Salesman Tour, The Steiner Tree, and the k-MST. A second objective is to consider less tractable problems such as partitioning and clustering, and also variants such as online approximation algorithms. A final objective is to consider limits of these techniques, for example hardness results for finding separators or spanners in more general metric spaces.
