3 papers
cs.DS2026
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, servers and requests lie in a metric space. Servers are available upfront, and requests arrive sequentially. An arriving request must…
cs.DS2026
Availability is all you need: achieving optimal regret with minimal information for dynamic matching
Süleyman Kerimov, Pengyu Qian, Mingwei Yang +1
We study a centralized discrete-time dynamic two-way matching model with finitely many agent types. Agents arrive stochastically over time and join their type-dedicated queues wait…
cs.DS2025
Online Metric Matching: Beyond the Worst Case
Mingwei Yang, Sophie H. Yu
We study the online metric matching problem. There are servers and requests located in a metric space, where all servers are available upfront and requests arrive one at a…