开车软件的匹配算法新思路：局部剪枝再全局优化

打车软件的核心问题：乘客请求来了，怎么在最短时间内匹配最近的司机？经典在线匹配要求立即做决定。但真实瓶颈往往是通信带宽——每个乘客只能知道附近少数司机。这篇论文形式化了这个问题。

核心设定：每个到达的乘客必须把可匹配司机集剪枝到最多 k 个候选项，然后中心协调器在这 k 个候选中做全局优化。

理论结果：在"充分 spread"条件下，局部剪枝后的全局匹配仍然近似最优。纽约市打车数据验证有效。

"信息约束下的全局优化"的漂亮抽象，从打车到云计算都适用。

论文信息

• 标题：Stochastic Matching via Local Sparsification
• 作者：Sara Ahmadian, Edith Cohen, Mohammad Roghani
• 预印本：arXiv:2605.14195 (cs.DS)
• 论文链接：https://arxiv.org/abs/2605.14195