In low distortion metric embeddings, the goal is to embed a host "hard" metric space into a "simpler" target space , while approximately preserving pairwise distances. A highly desirable target space is that of a tree metric. Unfortunately, such embedding will result in a huge distortion. A celebrated bypass to this problem is stochastic embedding with logarithmic expected distortion. Another bypass is Ramsey type embedding, where the distortion guarantee applies only to a subset of the points. However both this solutions fail to provide an embedding into a single tree with worst case distortion guarantee on all pairs. In this paper  we propose a novel third bypass called clan embedding. Here each point x is mapped to a subset of points f(x) ( called a clan ) with a special chief point \chi(x)\in f(x). The clan embedding has multiplicative distortion t if for every pair  x,y  some copy y'\in f(y) in the clan of y is close to the chief of x: \min_{y'\in f(y)}d(y',\chi(x))\le t\cdot d(x,y). Our first result is  clan embedding into a tree with multiplicative distortion O(\frac{\log n}{\epsilon}) such that each point has 1+\epsilon copies (in expectation). In addition, for graphs we provide a "spanning" version of this theorem , and use it to devise the first compact routing scheme with constant size routing tables. Next we turn to minor free graphs , who were previously stochastically embedded into bounded treewidth graphs with expected additive distortion \epsilon D (D being the diameter) . We devise a Ramsey type embedding and clan embedding analogs of the stochastic embedding. We use this embeddings to construct the first (bicriteria quasi-polynomial ) approximation schemes for the metric \rho-dominating set and metric \rho-independent set problems in minor free graphs.
In low distortion metric embeddings, the goal is to embed a host "hard" metric space into a "simpler" target space while approximately preserving pairwise distances. A highly desirable target space is that of a tree metric. Unfortunately, such embedding will result in a huge distortion. A celebrated bypass to this problem is stochastic embedding with logarithmic expected distortion. Another bypass is Ramsey-type embedding, where the distortion guarantee applies only to a subset of the points. However , both these solutions fail to provide an embedding into a single tree with a worst-case distortion guarantee on all pairs. In this paper , we propose a novel third bypass called clan embedding. Here each point x is mapped to a subset of points f(x) , called a clan , with a special chief point \chi(x)\in f(x). The clan embedding has multiplicative distortion t if for every pair ( x,y ) some copy y'\in f(y) in the clan of y is close to the chief of x: \min_{y'\in f(y)}d(y',\chi(x))\le t\cdot d(x,y). Our first result is a clan embedding into a tree with multiplicative distortion O(\frac{\log n}{\epsilon}) such that each point has 1+\epsilon copies (in expectation). In addition, we provide a "spanning" version of this theorem for graphs and use it to devise the first compact routing scheme with constant size routing tables. We then focus on minor-free graphs of diameter prameterized by D, which were known to be stochastically embeddable into bounded treewidth graphs with expected additive distortion \epsilon D . We devise Ramsey-type embedding and clan embedding analogs of the stochastic embedding. We use these embeddings to construct the first (bicriteria quasi-polynomial time) approximation scheme for the metric \rho-dominating set and metric \rho-independent set problems in minor-free graphs.
D
,
R
Ramsey type
Ramsey-type
R
both this
, both these
R
worst case
a worst-case
A
,
R
(
,
R
)
,
A
(
A
)
A
a
D
for graphs
R
,
for graphs
R
Next we turn to minor free graphs , who were previously stochastically embedded
We then focus on minor-free graphs of diameter prameterized by D, which were known to be stochastically embeddable
D
(D being the diameter)
R
a Ramsey type
Ramsey-type
R
this
these
R
) approximation schemes
time) approximation scheme
R
minor free
minor-free