{"ID":2851037,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.20288","arxiv_id":"2510.20288","title":"Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion","abstract":"In the online metric matching problem, $n$ servers and $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$, 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)$-competitive algorithm for $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)$ competitive ratio for non-trivial metrics beyond the i.i.d. setting. Our approach bypasses the $Ω(\\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.","short_abstract":"In the online metric matching problem, $n$ servers and $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...","url_abs":"https://arxiv.org/abs/2510.20288","url_pdf":"https://arxiv.org/pdf/2510.20288v5","authors":"[\"Yingxi Li\",\"Ellen Vitercik\",\"Mingwei Yang\"]","published":"2025-10-23T07:19:00Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}