Greedy matching method analyzed for random points in space
Optimal Analysis of Greedy for Stochastic Online Euclidean Matching
Data Structures and Algorithms
Summary
Matching things quickly and well is hard when points appear randomly in space. This paper studies a simple greedy strategy that pairs each new point with the closest available spot. The authors show that this approach works consistently well in most dimensions except two, where its performance grows slowly with more points. This improves understanding of how well a basic method handles random spatial matching problems.
What this means in practice
- •For network schedulers: Design online resource allocation methods knowing greedy matching performs reliably for random spatial requests in typical dimensions.
- •For robotic path planners: Improve online pairing of robots to tasks distributed randomly in space using proven bounds on greedy assignment cost.
A theory result. No direct application yet.
Authors
Mingwei Yang, Sophie H. Yu
Abstract
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\ne2$, and $Θ(\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.