The Taub Faculty of Computer Science Events and Talks

A finite metric space $(X,d)$ on a set of points $X$ is just the shortest path metric $d$ on a positively weighted graph $G=(X,E)$. In the online setting, the vertices of the input finite metric space $(X,d)$ are exposed one by one, together with their distances $d(*,*)$

to the previously exposed vertices. The goal is to embed (map) $X$ into a given host metric space $(H,d_H)$ (finite or not) and so to distort the distances as little as possible (distortion is the worst case ratio of how the distance is expanded, assuming it is never contracted).

I will start by a short survey on the main existing results of offline embedding into $ell_1, ell_2, ell_{infty}$ spaces. Then will present some results on online embedding: mainly lower bounds (on the best distortion) for small dimensional spaces, and some upper bounds for 2-dim Euclidean spaces.

As an intriguing question: the "rigid" $K_5$ metric space is a metric space on $G=K_5$, in which each edge should be thought as a unit interval $[0,1]$. The points are the $5$ fixed vertices of $K_5$ (that are exposed first) in addition to $n$ points that are arbitrarily placed anywhere in the edges, and exposed one by one. It is easy to show that an offline embedding into the $2$-dim Euclidean results in a distortion $Omega(n)$. What can be achieved in the online case ?? It was "believed" that an exponential distortion could be proven. We show that the distortion is bounded by $O(n^2)$.

The talk is based on joint work with Noam Licht and Yuri Rabinovich