Abstract
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 of 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 approx 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 \times X and with respect to K * X.
Moreover, our embeddings have implications to the areas of Approximation and Online Algorithms. In particular, Arora et. al. devised an ~O(sqrt(log(r))approximation algorithm for sparsestcut instances with r demands. Building on their framework, we provide an ~O(sqrt(log K)approximation for sparsestcut instances in which each demand is incident on one of the vertices of K (aka, terminals). Since K <= r, our bound generalizes that of Arora et al.
BibTeX  Entry
@InProceedings{elkin_et_al:LIPIcs:2015:5306,
author = {Michael Elkin and Arnold Filtser and Ofer Neiman},
title = {{Terminal Embeddings}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
pages = {242264},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897897},
ISSN = {18688969},
year = {2015},
volume = {40},
editor = {Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5306},
URN = {urn:nbn:de:0030drops53064},
doi = {10.4230/LIPIcs.APPROXRANDOM.2015.242},
annote = {Keywords: embedding, distortion, terminals}
}
Keywords: 

embedding, distortion, terminals 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) 
Issue Date: 

2015 
Date of publication: 

13.08.2015 