Optimal analysis of Greedy for stochastic online Euclidean matching: flat torus to the rescue

Abstract

We study online metric matching with $n$ servers and $n$ requests, all sampled independently and uniformly from $[0,1{]}^d$. We analyze the Greedy algorithm, which matches each arriving request to its closest available server. Despite its strong empirical performance, non-trivial bounds on Greedy's competitive ratio were previously known only for $d=1$, where it is $O(1)$-competitive [BFP23]. We prove that Greedy is $O(1)$-competitive for every fixed $d\ge 3$ and has competitive ratio $\Theta (\sqrt{\log n})$ for $d=2$. Our proof first analyzes Greedy on the flat torus and then transfers the resulting estimates to the cube.