Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings

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 O(log n) ⋅ min √ log Φ, √ n (or, O(d) ⋅ min √ log Φ, √ n 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)).

Next, we study the problem of online minimum-weight perfect matching (MWPM). Here a sequence of 2n points s 1 , . . . s 2n in a metric space arrive in pairs, and one has to maintain a perfect matching on the first 2i points S i = s 1 , . . . s 2i . We allow recourse (as otherwise the order of arrival determines the matching). The goal is to return a perfect matching that approximates the minimum-weight perfect matching on S i , while minimizing the recourse. Online matchings are among the most studied online problems, however, there is no previous work on online MWPM. One potential reason for this is that online MWPM is drastically non-monotone, which makes online optimization highly challenging. Our third result is a randomized algorithm with competitive ratio O(d ⋅ log Φ) and recourse O(log Φ) against an oblivious adversary, this result is obtained via our new stochastic online embedding. Our fourth result is a deterministic algorithm that works against an adaptive adversary, using O(log 2 n) recourse, and maintains a matching of total weight at most O(log n) times the weight of the MST, i.e., a matching of lightness O(log n). We complement our upper bounds with a strategy for an oblivious adversary that, with recourse r, establishes a lower bound of Ω( log n r log r ) for both competitive ratio as well as lightness.