Title: Terminal Embeddings

Authors: Michael Elkin, Arnold Filtser and Ofer Neiman.

Abstract: In this paper we study {\em terminal embeddings}, in which one is given a finite metric $(X,d_X)$ (or a graph 
$G=(V,E)$) and a subset $K \subseteq X$ of its points are designated as {\em 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 $\approx|K|\cdot |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 {\em 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 \times  X$ and with respect to $K \times X$.

Moreover, our embeddings have implications to the areas of 
Approximation and Online Algorithms. In particular, \cite{ALN08} devised an $\tilde{O}(\sqrt{\log r})$-approximation 
algorithm for sparsest-cut instances with $r$ demands. Building on their framework, we provide an 
$\tilde{O}(\sqrt{\log |K|})$-approximation for sparsest-cut instances in which each demand is incident on one of the 
vertices of $K$ (aka, terminals). Since $|K| \le r$, our bound generalizes that of \cite{ALN08}.