arXiv preprint ·
Optimal Analysis of Greedy for Stochastic Online Euclidean Matching
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
The Inverse Lyndon Array
High-Dimensional Ultra-Log-Concave Distributions
An Arboricity-Sensitive Algorithm for the $K_r-e$-Free Graph Sandwich Problem
Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata
Single-Pass Estimation of the Clustering Coefficient Distribution in Graph Streams
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.