Graduate Seminar on Algorithms and Optimization (S4C3): Metric Embeddings and Applications

The course will focus on the theory of metric embeddings, where we aim to construct mappings between metric spaces such that distances are approximately preserved. Such mappings allow us to represent a given metric space in a simplified way;
if a computational problem can be solved over some simple class of metric spaces and we can embed any metric space into this class with low distortion, an approximation algorithm for the problem on general metrics will usually follow.
Canonical examples of restricted classes of metric spaces include the shortest-path metrics of trees, or the metrics of finite subsets of (low-dimensional) real vector spaces equipped with a p-norm.

Potential topics for this seminar include the construction of low-distortion embeddings, the relationship between metric embeddings and low-diameter decompositions, and applications of metric embeddings in approximation algorithms.

You can find the slides from the seminar pre-meeting here.