Optimal Analysis of Greedy for Stochastic Online Euclidean Matching

We study Greedy for online metric matching with $n$ servers and $n$ requests sampled independently and uniformly from $[0,1{]}^d$. Servers are available initially, and Greedy irrevocably matches each arriving request to its closest available server, incurring a cost of their distance. We prove that Greedy has competitive ratio $O(1)$ for every fixed $d\mathrm{\ne }2$, and $\mathrm{\Theta }(\sqrt{\log n})$ for $d=2$. Previously, constant competitiveness was shown for $d=1$ [BFP23], and no non-trivial results for this setting were known for higher dimensions. Our proof first analyzes Greedy on the flat torus and then transfers the estimates back to the cube.