Online Metric Matching: Beyond the Worst Case
提出一种新的算法框架，利用骑手位置的额外信息（如独立采样或不可信预测）来改进在线度量匹配中的匹配决策，在随机到达和预测模型下分别实现了更优的竞争比和遗憾保证。
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.