Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings

Abstract

Low-distortional metric embeddings are a crucial component in the modern algorithmic toolkit. In an online metric embedding, points arrive sequentially and the goal is to embed them into a simple space irrevocably, while minimizing the distortion. Our first result is a deterministic online embedding of a general metric into Euclidean space with distortion if the metric has doubling dimension d), solving affirmatively a conjecture by Newman and Rabinovich (2020), and quadratically improving the dependence on the aspect ratio Φ from Indyk et al. (2010). Our second result is a stochastic embedding of a metric space into trees with expected distortion O(d·log Φ), generalizing previous results (Indyk et al. (2010), Bartal et al. (2020)).

Locations

• arXiv (Cornell University) - View - PDF
• Society for Industrial and Applied Mathematics eBooks - View