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

arXiv:2609.23947 · cs.DS · Submitted 2026-09-20 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Optimal analysis of Greedy for stochastic online Euclidean matching".

Jane: Here's the gist of the paper. Optimal Analysis of Greedy for Stochastic Online Euclidean Matching proves that Greedy has competitive ratio O(1) for every fixed dimension d!= 2 and is O(√log n)-competitive for d = 2.

Tom: Model and Setup The study focuses on online metric matching with n servers and n requests sampled independently and uniformly from

0, 1: d.

Jane: Servers are available initially, and Greedy irrevocably matches each arriving request to its closest available server, incurring a cost of their distance.

Tom: The objective is to minimize the total matching cost without observing future requests.

Paper summary: Tom: So looking at the title "Optimal analysis of Greedy for stochastic online Euclidean matching: flat torus to the rescue," it’s clear they’re talking about how they used this torus structure as a way to fix a problem with boundary effects.

Jane: Exactly, so the main implication is that by studying it on a flat torus, they manage to remove those nasty boundary issues that plague the analysis in the standard Euclidean cube.

Lu: The authors are showing that this technique of analyzing it on a simpler space first and then transferring those estimates back to the more complex space isn't just some academic trick.

Meng: It’s about showing that for many online matching problems, you can simplify the geometry temporarily to get strong initial guarantees before tackling the full complexity.

Tom: And for someone who only listens to this show, it means that when you’re designing an online system, if you deal with a problem where boundary conditions matter, this paper suggests looking at simpler models first to establish some baseline performance before building up the full complexity of the Euclidean space.

Jane: It’s about establishing a clear separation between dimensions three and higher where things are stable, and dimension two where things exhibit that unique structure that requires a special kind of analysis.

Lu: The paper proves that this specific allocation rule is not universally good across all dimensions, which is why the competitive ratio shifts from constant to something dependent on the dimension.

Meng: It’s a clear statement about the limitations of relying solely on a greedy approach when you can’t guarantee what happens near those boundaries.

Tom: So, in short, this paper gives us concrete performance guarantees for Greedy in these specific settings, showing it's O one competitive for most dimensions and root log n competitive for two dimensions.

Conclusion: Tom: So, we're wrapping up our look at this paper, "Optimal analysis of Greedy for stochastic online Euclidean matching: flat torus to the rescue." Essentially, they’re taking a standard greedy matching algorithm and proving exactly how good it is under random arrivals in those high-dimensional spaces.

Jane: I think the title itself tells you what's happening here—the flat torus is this trick they use to get a clean analysis when dealing with these weird boundary conditions in Euclidean space. It’s about making sure the performance holds up even when things are distributed around a periodic shape instead of just an infinite plane.

Lu: What the authors actually do is show that for most dimensions, this greedy approach is very strong, achieving constant competitive ratio—that means it's close to optimal in terms of total cost.

Meng: And they nail that for all dimensions except two, where they get a weaker guarantee, which is logarithmic with respect to the number of requests. That’s a big distinction when you’re trying to deploy something at scale.

Tom: So the main point is that in most cases, you can rely on this simple greedy rule without worrying too much about performance degradation as things get bigger or more complex in the dimension.

Jane: But they also establish a lower bound for those two dimensions, showing that you can’t do better than something that scales with the square root of the logarithm of the number of requests. That sets a clear limit on what any algorithm can possibly achieve in those specific two-dimensional scenarios.

Lu: It’s about establishing that this greedy strategy isn't universally perfect across every single dimension, which is a necessary piece for understanding where these types of online matching algorithms actually stand.

Meng: For me, the implication is that if you’re building a system and you know your data lives in a space with many dimensions, you can be confident in this greedy method performing well without needing super complicated math.

Tom: It sounds like they've given us a solid performance roadmap for when we’re dealing with these kinds of random inputs on geometric structures. Next up, we’ll look at how this relates to other online matching problems where the input structure is different entirely.

Stanford University · Wharton School of Business, University of Pennsylvania

cs.DS

Submitted: 2026-09-20

Updated: 2026-11-04

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 100/100

The gist: Optimal Analysis of Greedy for Stochastic Online Euclidean Matching proves that Greedy has competitive ratio O(1) for every fixed dimension d!= 2 and is O(√log n)-competitive for d = 2.

Key concepts

Competitive Ratio (CRn)
This measures how much worse the expected cost of a greedy online algorithm is compared to the best possible offline matching. A ratio close to 1 means the algorithm performs very well, while a large ratio indicates poor performance.
Flat Torus
The flat torus is a periodic cube used in the analysis. It simplifies the problem by removing boundary effects and restoring translation symmetry, allowing researchers to study server and request distributions more easily.
Greedy Matching
This is an online strategy where each arriving request is immediately matched to the closest available server based on Euclidean distance. The algorithm makes decisions without knowing future requests, aiming to minimize the total matching cost.

Terminology

Summary

Optimal Analysis of Greedy for Stochastic Online Euclidean Matching proves that Greedy has competitive ratio O(1) for every fixed dimension d! p. 0= 2 and is O(√log n)-competitive for d = 2. p. 0

Model and Setup

The study focuses on 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. p. 0 The objective is to minimize the total matching cost without observing future requests. p. 1 The competitive ratio CRn is defined as the ratio of expected costs, EGn/EOPTn, where both expectations are over the independent server and request samples. p. 5

Analysis on the Flat Torus

The analysis begins by studying Greedy on the flat torus (periodic cube), which removes boundary effects and restores translation symmetry. Fact 1 states that for every measurable region P, EBm ∩ P = mP, implying torus stationarity. p. 6 The analysis uses the Efron–Stein inequality to bound the variance of server counts, yielding a tail bound for the total matching cost on the torus at scale r. p. 2

Comparison Between Torus and Cube

The comparison between Greedy on the torus and Euclidean Greedy in the cube is achieved by opening the torus into a cube via a uniformly random cut U. Lemma 7 shows that unwrapping the process under dU gives exactly the Euclidean Greedy process on transformed inputs, allowing for cost and server-count estimates to be transferred. p. 3 The discrepancy between the two processes is bounded by EKm = O(min[m, Mn]). p. 3

Competitive Ratio Bounds

Theorem 1 establishes that Greedy is O(1)-competitive for d!= 2 and O(√log n)-competitive for d = 2. p. 0 p. 0 The lower bound proof for d = 2 establishes that Greedy is Ω(√log n)-competitive. p. 1 The analysis relies on the deficit of a cell P as the positive difference between mP, the expected number of future requests landing in P, and its remaining-server count. p. 3 The final lower bound is established by showing that the expected total deficit in (41) is at most cdefTm/2 for every admissible rank m. p. 3

Key Technical Results

The analysis heavily relies on Lemma 6, which bounds the total variance of server counts over any partition without a factor for the number of cells. Lemma 10 bounds the normalized expected-count error Hm = O(min[m, Mn]/m). p. 3 The analysis of the geometric sensitivity bound is crucial for controlling distance increments. p. 4 The final step involves bounding the expected cost by integrating the tail probability, leading to EGn = O(Mn). p. 2

Related Literature

The paper relates its findings to prior work on adversarial input and random order. It contrasts the results with studies on random input, noting that constant-competitive algorithms are known for d >= 3. p. 4 The analysis of Greedy under random input is compared to prior results on the line. p. 2 The work builds upon analyses that exploit the order structure of the line, which cannot be easily generalized to higher dimensions. p. 5

Appendix Details

Appendix A provides proofs for Fact 1 and Fact 2, demonstrating the translation invariance and the properties of random cuts. Appendix A. p. 7 p. 7 p. 7 p. 74 proves Lemma 3 using a scalar potential function related to the increase in squared distance. p. 8 The proof of Lemma 15 involves a complex bookkeeping device where a mark tracks the extra server's location. The final bound relies on the cell-containment property and the fourth-moment formula for binomial variables. p. 3 The acknowledgement notes that the proof was discovered by GPT 5. p. 06 Sol during an interactive process guided by the authors. p. 0 p. 0

References

[AALS22] Mohammad Akbarpour, Yeganeh Alimohammadi, Shengwu Li, and Amin Saberi. The value of excess supply in spatial matching markets. p. 1 In EC, page 62.

[ABCG26] Josh Ascher, Eric Balkanski, Jason Chatzitheodorou, and Vasilis Gkatzelis. p. 4 Online min-cost matching with general arrivals. p. 4 CoRR, abs/2606.05546, 2026. p. 0

[AKS14] Dror Aiger, Haim Kaplan, and Micha Sharir. p. 8 Reporting neighbors in high-dimensional euclidean space. p. 8 SIAM J. Comput., 43(4):1363–1395, 2014.

[AKT84] Mikl´os Ajtai, J´anos Koml´os, and G´abor Tusn´ady. On optimal matchings. p. 2 Combinatorica, 4(4):259–264, 1984.

[Aro98] Sanjeev Arora. p. 8 Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. p. 8 J. ACM, 45(5):753–782, 1998.

[BBGN14] Nikhil Bansal, Niv Buchbinder, Anupam Gupta, and Joseph Naor. p. 4 A randomized o(log2 k)-competitive algorithm for metric bipartite matching. p. 4 Algorithmica, 68(2):390–403, 2014.

[BBI01] Dmitri Burago, Yuri D. Burago, and Sergei Ivanov. A Course in Metric Geometry, volume 33. p. 0 American Mathematical Society, 2001.

[BBLM05] St´ephane Boucheron, Olivier Bousquet, G´abor Lugosi, and Pascal Massart. p. 5 Moment inequalities for functions of independent random variables. p. 2 The Annals of Probability, 33(2):514–560, 2005. p. 2

[BFP23] Eric Balkanski, Yuri Faenza, and No´emie P´erivier. p. 0 The power of greedy for online minimum cost matching on the line. p. 1 In EC, pages 185–205. ACM, 2023.

[BL21] Sergey G Bobkov and Michel Ledoux. A simple fourier analytic proof of the akt optimal matching theorem. p. 2 The Annals of Applied Probability, 31(6):2567–2584, 2021. p. 2

[CKKZ26] Yilun Chen, Yash Kanoria, Akshit Kumar, and Wenxin Zhang. p. 1 Feature-based dynamic matching. p. 5 Oper. Res., 74(2):788–803, 2026. p. 0

[DFG99] Qiang Du, Vance Faber, and Max Gunzburger. p. 8 Centroidal voronoi tessellations: Applications and algorithms. p. 8 SIAM review, 41(4):637–676, 1999.

[GGPW19] Anupam Gupta, Guru Guruganesh, Binghui Peng, and David Wajc. p. 4 Stochastic online metric matching. p. 0 In ICALP, volume 132 of LIPIcs, pages 67:1–67:14. p. 3 Schloss Dagstuhl - Leibniz-Zentrum f¨ur Informatik, 2019.

[GK19] Martin Gairing and Max Klimm. p. 1 Greedy metric minimum online matchings with random arrivals. p. 4 Oper. Res. Lett., 47(2):88–91, 2019.

[HPZ21] Nina Holden, Yuval Peres, and Alex Zhai. p. 2 Gravitational allocation for uniform points on the sphere. p. 2 2021.

[HTW24] Zhiyi Huang, Zhihao Gavin Tang, and David Wajc. p. 1 Online matching: A brief survey. p. 1 SIGecom Exch., 22(1):135–158, 2024.

[Kan25] Yash Kanoria. p. 2 Dynamic spatial matching. p. 1 The Annals of Applied Probability, 35(5):3086–3118, 2025. p. 2

[KMV94] Samir Khuller, Stephen G. p. 1 Mitchell, and Vijay V. Vazirani. On-line algorithms for weighted bipartite matching and stable marriages. p. 4 Theor. Comput. Sci., 127(2):255–267, 1994.

[KP93] Bala Kalyanasundaram and Kirk Pruhs. p. 1 Online weighted matching. p. 1 J. Algorithms, 14(3):478–488, 1993. p. 1

[Kum26] Akshit Kumar. p. 5 Feature-based dynamic matching in the dark. p. 5 Available at SSRN 6839679, 2026. p. 0

[KVV90] Richard M. p. 1 Karp, Umesh V. Vazirani, and Vijay V. Vazirani. An optimal algorithm for on-line bipartite matching. p. 4 In STOC, pages 352–358. ACM, 1990.

[LVY26] Yingxi Li, Ellen Vitercik, and Mingwei Yang. p. 0 Smoothed analysis of online metric matching with a single sample: Beyond metric distortion. p. 0 In ITCS, volume 362 of LIPIcs, pages 94:1–94:23. p. 3 Schloss Dagstuhl - Leibniz-Zentrum f¨ur Informatik, 2026. p. 0

[MNP06] Adam Meyerson, Akash Nanavati, and Laura J. p. 4 Poplawski. Randomized online algorithms for minimum metric bipartite matching. p. 4 In SODA, pages 954–959. ACM Press, 2006.

[MSVV07] Aranyak Mehta, Amin Saberi, Umesh V. p. 1 Vazirani, and Vijay V. Vazirani. Adwords and generalized online matching. p. 0 J. ACM, 54(5):22, 2007.

[PS23] Enoch Peserico and Michele Scquizzato. p. 4 Matching on the line admits no o(√log n)-competitive algorithm. p. 4 ACM Trans. Algorithms, 19(3):28:1–28:4, 2023. p. 1

[Rag16] Sharath Raghvendra. p. 4 A robust and optimal online algorithm for minimum metric bipartite matching. p. 1 In APPROX-RANDOM, volume 60 of LIPIcs, pages 18:1–18:16. p. 3 Schloss Dagstuhl - Leibniz-Zentrum f¨ur Informatik, 2016.

[Rag18] Sharath Raghvendra. p. 4 Optimal analysis of an online algorithm for the bipartite matching problem on a line. p. 4 In SoCG, volume 99 of LIPIcs, pages 67:1–67:14. p. 3 Schloss Dagstuhl - Leibniz-Zentrum f¨ur Informatik, 2018.

[Sib80] Robin Sibson. p. 9 A vector identity for the dirichlet tessellation. p. 9 In Mathematical Proceedings of the Cambridge Philosophical Society, volume 87, pages 151–155. p. 3 Cambridge University Press, 1980. p. 0

[Ste86] J. Michael Steele. An Efron–Stein inequality for nonsymmetric statistics. p. 2 The Annals of Statistics, 14(2):753–758, 1986.

[Tal92] Michel Talagrand. Matching random samples in many dimensions. p. 5 The Annals of Applied Probability, pages 846–856, 1992. p. 2

[Tal22] Michel Talagrand. p. 2 Upper and lower bounds for stochastic processes: decomposition theorems. p. 4 Springer Nature, 2022.

[Tao12] Terence Tao. Higher order Fourier analysis. p. 5 American Mathematical Soc., 2012.

[TSD+16] Yongxin Tong, Jieying She, Bolin Ding, Lei Chen, Tianyu Wo, and Ke Xu. p. 1 Online minimum matching in real-time spatial data: experiments and analysis. p. 1 Proceedings of the VLDB Endowment, 9(12):1053–1064, 2016.

[TTC94] Ying The Tsai, Chuan Yi Tang, and Yunn Yen Chen. p. 5 Average performance of a greedy algorithm for the on-line minimum matching problem on euclidean space. p. 1 Inf. Process. Lett., 51(6):275–282, 1994.

[YY26] Mingwei Yang and Sophie H. p. 0 Yu. Online metric matching: Beyond the worst case. p. 1 Oper. Res., 74(1):130–140, 2026. p. 0

Appendix A Summary

Appendix A collects proofs and references for the facts and lemmas stated in Section 2 through 35. Appendix A.1 proves Fact 1 by showing that simultaneous translation leaves the joint distribution of servers and requests unchanged. p. 2 Appendix A.3 provides the source for Lemma 2. p. 1 Appendix A.4 proves Lemma 3 by analyzing the increase in squared distance as a scalar potential. p. 8

Section 5 Summary

Section 5 proves Theorem 2 by establishing the lower bound for d = 2. The proof proceeds by defining an admissible rank m and showing that EG[cTm,m] = Ω(√n). p. 5 This is achieved by transferring a lower bound on the total server deficit in the torus grid to the square grid via Lemma 12. p. 3 The final result shows that EGn = O(Mn). p. 5

Final Conclusion

The paper concludes that in every dimension, EGn = O(Mn). This upper bound is compared against the offline matching scales EOPTn, yielding the competitive-ratio upper bounds. p. 0 The lower bound for d=2 yields EGn = Ω(√n log n). p. 3 The overall result is that Greedy is O(1)-competitive for d! p. 3= 2 and O(√log n)-competitive for d = 2. The paper acknowledges that the proof was discovered by GPT 5. p. 06 Sol during an interactive process guided by the authors.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved competitive analysis for Greedy in higher dimensions by proving O(1) competitiveness for d >= 3 based on analysis of flat torus and cube comparisons. This allows AI systems to guarantee constant competitive ratios across various spatial environments when the input distribution is uniform in a high dimension.

  2. Enhanced understanding of the performance gap between Greedy and optimal matching specifically for dimension two, demonstrating that even under independent uniform input, Greedy does not attain the order of the expected offline optimum as in other dimensions. This enables AI designers to recognize structural differences in optimal matchings for d=2 versus d!=2.

  3. Development of a robust framework to transfer performance guarantees from a symmetric periodic setting (flat torus) to the actual Euclidean space cube via random cuts, ensuring that conditional on U, the transformed inputs, unmatched server configurations at all ranks, and matching costs jointly have the law of the original cube Greedy process. This allows AI systems operating in Euclidean space to leverage simpler theoretical bounds derived from translation symmetry.

  4. A method to derive sharp lower bounds for dimension two by analyzing server deficits in square grid cells using a combination of torus deficit transfer and request fluctuations. This enables AI researchers to establish a tight lower bound of Theta(sqrt(log n)) for d=2, precisely characterizing the performance limit of the Greedy algorithm in this specific dimension.

Sources

Related papers