Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion

Yingxi Li, Ellen Vitercik, Mingwei Yang

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…