Deterministic Online Embedding of Metric Spaces into Low Dimensional Spaces

Noam Licht, Ilan Newman, Yuri Rabinovich

We study online embeddings of metric spaces into Euclidean spaces of a constant dimension $d>1$, against an adaptive adversary. While the case of $d=1$ is well understood, for high…