• Calendar

June 5, Tuesday
12:00 – 14:00

Metric embeddings has been a useful tool in designing approximation algorithms in the last decade. One of the basic paradigm in which it is employed is as follows: Given a hard optimization problem over metric data $X$, first embed $f:X \rightarrow H$, and then solve the problem over $f(X)$, assuming that H is a "nice" metric space to optimize over. One such a successful approach is "probabilistic embedding into trees" due to Alon, Karp, Peleg, West, and Bartal. This metric embedding technique is useful for minimization problems over distances in which the optimized function is linear, and (relatively) easy to solve on trees.

In this talk, I will describe a strengthening of the probabilistic embedding, that enable reducing a class of NONLINEAR problems (mainly nonlinear clustering problems) to trees.

Based on a joint work with Assaf Naor