Terminal embeddings
Michael Elkin, Arnold Filtser, Ofer Neiman · Theoretical Computer Science · 2017
In this paper we study terminal embeddings , in which one is given a finite metric ( X , d X ) (or a graph G = ( V , E ) ) and a subset K ⊆ X of its points are designated as terminals . The objective is to embed the metric into a normed space, while approximately preserving all distances among pairs that contain a terminal. We devise such embeddings in various settings, and conclude that even though we have to preserve ≈ | K | ⋅ | X | pairs, the distortion depends only on | K | , rather than on | X | . We also strengthen this notion, and consider embeddings that approximately preserve the distances between all pairs, but provide improved distortion for pairs containing a terminal. Surprisingly, we show that such embeddings exist in many settings, and have optimal distortion bounds both with respect to X × X and with respect to K × X . Moreover, our embeddings have implications to the areas of Approximation and Online Algorithms. In particular, [10] devised an O ˜ ( log r ) -approximation algorithm for sparsest-cut instances with r demands. Building on their framework, we provide an O ˜ ( log | K | ) - approximation for sparsest-cut instances in which each demand is incident on one of the vertices of K (aka, terminals). Since | K | ≤ r , our bound generalizes that of [10] .