Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion
Yingxi Li, Ellen Vitercik, Mingwei Yang · 2025
Read Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion by Yingxi Li, Ellen Vitercik, Mingwei Yang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-20288.txt.
Introduction
Yingxi Li, Ellen Vitercik, and Mingwei Yang study online metric matching under smoothed analysis with only a single sample from each request distribution. Servers sit in a Euclidean space and requests arrive one by one, each needing an immediate, permanent match to a free server at a cost equal to distance. Servers are adversarial, while requests come from distinct distributions meeting a mild smoothness condition.
The authors give a constant-competitive algorithm for every dimension except two that needs no knowledge of the distributions beyond one sample each. Their analysis bypasses the usual metric embedding barrier by bounding the algorithm cost directly on the target metric of a simple deterministic embedding. Lower bounds on the offline optimum from majorization arguments complete the guarantee.
Catalog record
| CREATOR | Yingxi Li, Ellen Vitercik, Mingwei Yang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 64 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-20288
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion Yingxi Li, Ellen Vitercik, Mingwei Yang Abstract In the online metric matching problem, n n servers and n n requests lie in a metric space. Servers are available upfront, and requests arrive sequentially. An arriving request must be matched immediately and irrevocably to an available server, incurring a cost equal to their distance. The goal is to minimize the total matching cost. We study this problem in the Euclidean metric [ 0 , 1 ] d [0,1]^{d} , when servers are adversarial and requests are independently drawn from distinct distributions that satisfy a mild smoothness condition. Our main result is an O ( 1 ) O(1) -competitive algorithm for d ≠ 2 d\neq 2 that requires no distributional knowledge, relying only on a single sample from each request distribution. To our knowledge, this is the first algorithm to achieve an o ( log n ) o(\log n) competitive ratio for non-trivial metrics beyond the i.i.d. setting. Our approach bypasses the Ω ( log n ) \Omega(\log n) barrier introduced by probabilistic metric embeddings: instead of analyzing the embedding distortion and the algorithm separately, we directly bound the cost of the algorithm on the target metric of a simple deterministic embedding. We then combine this analysis with lower bounds on the offline optimum for Euclidean metrics, derived via majorization arguments, to obtain our guarantees. 1 Introduction The online metric matching problem is a classic topic in the design of online algorithms and has been studied extensively for decades. In this problem, n servers are available upfront and n requests arrive sequentially, with all servers and requests lying in a common metric space. Each request must be immediately and irrevocably matched to an unmatched server, incurring a cost equal to their distance. The goal is to minimize the total matching cost. The online metric matching problem captures a variety of practical scenarios. In ride-hailing, for example, servers and requests correspond to drivers and passengers, and the cost of a match reflects the pickup distance. The Euclidean special case is also natural for applications such as kidney exchange, where patients and donors are represented by high-dimensional feature vectors and the Euclidean distance between them captures compatibility. When servers and requests are adversarially chosen, [ MNP06 ] give an O(\log^{3}n) -competitive algorithm for general metrics, later improved to O(\log^{2}n) [ BBGN14 ] . For Euclidean metrics, an O(\log n) -competitive algorithm is given by [ GL12 ] . On the other hand, there exists an \Omega(\log n) competitive-ratio lower bound for uniform metrics 1 1 1 A metric is uniform if every pair of distinct points has distance 1 . [ MNP06 ] , which holds even in the random-order arrival model [ Rag16 ] . Moreover, no algorithm can achieve an o(\sqrt{\log n}) competitive ratio for line metrics [ PS23 ] . The fully adversarial model is often considered overly pessimistic, since worst-case scenarios rarely arise in practice. A more realistic assumption is that requests are i.i.d. sampled, while servers remain adversarial. In this setting, [ GGPW19 ] give an O((\log\log\log n)^{2}) -competitive algorithm for general metrics and distributions, and their algorithm is O(1) -competitive for tree metrics. Recently, [ YY25 ] show that the above setting further reduces to the case where all servers and requests are i.i.d. sampled from the same distribution. Building on this, they obtain an O(1) -competitive algorithm for Euclidean metrics with smooth distributions, where a distribution is smooth if it admits a density with respect to the uniform measure upper bounded by a constant. The i.i.d. model yields nearly tight guarantees, but it is often unrealistic: in many applications, different requests follow markedly different distributions. A more promising approach is smoothed analysis , which has been widely successful in both theory and practice, and is frequently used to explain the strong empirical performance of heuristics with poor worst-case guarantees [ ST09 , CGVY24 , HRS24 , CU25 ] . In this model, the adversary specifies a smooth distribution over inputs, and the algorithm is required to perform well in expectation. In this paper, we adopt the smoothed analysis framework to study online metric matching and obtain improved competitive ratios under significantly weaker assumptions than those in the i.i.d. setting. 1.1 Our Results Main result. We focus on the Euclidean metric [0,1]^{d} , assuming that servers are adversarial and requests are independently drawn from distinct smooth distributions. As our main result, we give an algorithm which requires no knowledge of the distributions and is O(1) -competitive for d\neq 2 , given access to one sample from each of the n request distributions ( Theorem 5.1 ). In particular, the algorithm does not need to know the correspondence between distributions and samples, and its competitive ratio depends polynomially on d and the smoothness parameter, which are usually treated as constants that do not grow with n [ GL12 , Kan22 , YY25 ] . To the best of our knowledge, this is the first algorithm to achieve an o(\log n) competitive ratio for non-trivial metrics in a setting beyond the i.i.d. assumption, even when the request distributions are fully known to the algorithm (see Table 1 for a thorough comparison with prior work). Requests Servers Metric Space Distributional Knowledge Competitive Ratio Reference Adversarial Adversarial General None O(\log^{2}n) [ BBGN14 ] Adversarial Adversarial Euclidean None O(\log n) [ GL12 ] i.i.d. Adversarial General Full knowledge O((\log\log\log n)^{2}) [ GGPW19 ] i.i.d. Adversarial Tree Full knowledge O(1) [ GGPW19 ] i.i.d. smooth Adversarial Euclidean O(n^{2}) samples O(1) for d\neq 2 [ YY25 ] i.i.d. uniform Adversarial Euclidean Full knowledge O(1) [ YY25 ] Independent, non-identical, smooth Adversarial Euclidean One sample per distribution O(1) for d\neq 2 Our work Table 1: Comparison with prior work on online metric matching with the state-of-the-art results. Our result is the first to achieve an o(\log n) competitive ratio for nontrivial metrics under distributional assumptions strictly weaker than i.i.d. A complementary algorithm. In addition, we present a second algorithm under the same assumptions whose guarantees are not directly comparable ( Theorem 5.1 ). It is O(1) -competitive for d\geq 3 and, while still suboptimal in d=2 , it outperforms the first algorithm in that regime, providing a complementary strength. Discussion. Our sample-based assumption—one sample per request distribution—is a natural and practical assumption, widely adopted in recent work on online algorithms [ AKW14 , RWW20 , KNR22 , DKL+24 , GSW25 ] . This assumption is also necessary to some extent, as it is unclear how an algorithm could leverage the distributional properties of requests without some information, even in simpler i.i.d. settings. In comparison, our assumptions are weaker than those in prior work for the i.i.d. model: the algorithm of [ GGPW19 ] requires full knowledge of the distribution, and the algorithm of [ YY25 ] needs O(n^{2}) samples. Finally, we turn to the role of the dimension d . Two-dimensional space is a critical case for Euclidean matching: prior works highlight that the plane behaves fundamentally differently from both the line and higher dimensions [ Tal22 , Kan22 , YY25 ] . Consistent with this, our analysis