Online Metric Matching: Beyond the Worst Case
Mingwei Yang, Sophie H. Yu · Operations Research · 2025
New Algorithms for Online Metric Matching with Stochastic Arrivals or Predictions How do we match riders to drivers? Online metric matching offers a clean abstraction of this problem, where arriving riders are instantaneously matched to waiting drivers and the matching cost is measured by the pickup distance. Its challenge lies in making matching decisions without knowing the locations of future riders, for which the simple greedy approach yields suboptimal solutions. In their paper “Online Metric Matching: Beyond the Worst Case,” Yang and Yu propose a novel algorithmic framework of designing algorithms for online metric matching when given access to additional information of riders’ locations in advance. They then apply this framework to derive new algorithms when the riders’ locations are independently sampled or when an untrusted prediction of riders’ locations is provided. In the former model, their algorithms achieve improved competitive ratio and regret guarantees for various settings. In the latter model, they present an algorithm whose performance smoothly depends on the prediction error while preserving the worst-case guarantee.