arXiv:2605.14195cs.DScs.LG2026-05

在带宽受限的系统中,用局部压缩实现全局近优匹配。

Stochastic Matching via Local Sparsification

论文配图:Stochastic Matching via Local Sparsification
图 1 · 摘自论文原文
  • 先局部筛选兼容边至预算k,再全局优化匹配
  • 当解的分布足够分散时,能保持最大匹配期望大小
  • 适合实时网约车、分布式计算等带宽敏感场景

经典在线随机匹配问题通常要求即时且不可撤销的匹配决策。但在现代去中心化系统(如实时网约车和分布式云计算)中,主要瓶颈往往是本地通信带宽而非匹配时机。为此,我们提出两阶段局部稀疏化框架:到达的请求必须将实际兼容集合压缩至严格预算k条边后,再由中心协调器进行全局匹配优化。这在局部信息限制与全局优化收益间形成‘中间地带’。我们设计了一种基于期望实例分数解的局部选择策略。理论上,我们量化了近似比与解的‘分布范围’的关系;证明在足够分散的情况下,该稀疏化方法能全局保持最大匹配的期望规模。实验上,我们使用纽约市网约车数据集和对抗性合成基准验证了方法的鲁棒性。结果表明,即使在高度受限的本地预算下,仍可实现接近最优的全局匹配,显著优于标准在线基线。

原文摘要 · Abstract (English)

The classic online stochastic matching problem typically requires immediate and irrevocable matching decisions. However, in many modern decentralized systems such as real-time ride-hailing and distributed cloud computing, the primary bottleneck is often local communication bandwidth rather than the timing of the match itself. We formalize this challenge by introducing a two-stage local sparsification framework. In this setting, arriving requests must prune their realized compatibility sets to a strict budget of $k$ edges before a central coordinator optimizes the global matching. This creates a "middle ground" between local information constraints and global optimization utility. We propose a local selection strategy, parametrized by a fractional solution of the expected instance. Theoretically, we quantify the approximation ratio as a function of the solution's {\em spread}. We prove that under sufficient spread, our sparsifier globally preserves the expected size of the maximum matching. Empirically, we demonstrate the robustness of our approach using the New York City ride-hailing datasets and adversarial synthetic benchmarks. Our results show that near-optimal global matching is achievable even with highly constrained local budgets, significantly outperforming standard online baselines.

匹配算法稀疏化分布式系统

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。