Online Monotone Metric Embeddings
This work provides a new framework for online metric embeddings that overcomes fundamental lower bounds, benefiting algorithm designers who rely on HST embeddings for online problems.
The paper introduces online monotone metric embeddings, a relaxation that allows distances in the target space to decrease over time, breaking previous lower bounds and achieving O(log^2 n) distortion for embeddings into HSTs. For dynamic settings with up to l simultaneous points, probabilistic monotone embeddings achieve nearly optimal O(l log l) distortion.
Metric embeddings into structured spaces, particularly hierarchically well-separated trees (HSTs), are a fundamental tool in the design of online algorithms. In the classical online embedding setting, points arrive sequentially and must be embedded irrevocably upon arrival, resulting in strong distortion lower bounds of $Ω(\min(n, \log n\log Δ))$, where $n$ is the number of points and $Δ$ their aspect ratio. We propose a novel relaxation, \emph{online monotone metric embeddings}, which allows distances between embedded points in the target space to decrease monotonically over time. Such relaxed embeddings remain compatible with many online algorithms. Moreover, this relaxation breaks existing lower bound barriers, enabling embeddings into HSTs with distortion $O(\log^2 n)$. We also study a dynamic variant, where points may both arrive and depart, seeking distortion guarantees in terms of the maximum number $l$ of simultaneously present points. For traditional embeddings, such bounds are impossible, and this limitation persists even for deterministic monotone embeddings. Surprisingly, probabilistic monotone embeddings allow for $O(l \log l)$ distortion, which is nearly optimal given an $Ω(l)$ lower bound.