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

Mingwei Yang, Sophie H. Yu

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 arriv…