用聚类方法优化心脏移植匹配，理论性能逼近最优。
Near-Optimal Dynamic Matching via Coarsening with Application to Heart Transplantation
- 将离线器官节点聚类成有容量限制的组，提升匹配效率。
- 在真实数据模拟中达到0.91的竞争力比，远超美国现行政策的0.51。
- 适合关注医疗资源分配与在线匹配理论的研究者。
在线匹配在互联网广告和器官分配等领域广泛应用，但实际算法常缺乏坚实的理论保证。本文提出基于聚类的新型在线匹配算法，通过将离线节点聚合为有容量限制的集群，反向实现接近最优的理论性能。该方法应用于心脏移植分配，利用历史数据的结构特性设计出具有理论依据的策略。在基于真实数据的模拟中，新策略表现接近全知基准，竞争力比达0.91，显著优于美国现行政策的0.51。本工作弥合了数据驱动启发式方法与悲观理论下界之间的鸿沟。
原文摘要 · Abstract (English)
Online matching has been a mainstay in domains such as Internet advertising and organ allocation, but practical algorithms often lack strong theoretical guarantees. We take an important step toward addressing this by developing new online matching algorithms based on a coarsening approach. Although coarsening typically implies a loss of granularity, we show that, to the contrary, aggregating offline nodes into capacitated clusters can yield near-optimal theoretical guarantees. We apply our methodology to heart transplant allocation to develop theoretically grounded policies based on structural properties of historical data. Furthermore, in simulations based on real data, our policy closely matches the performance of the omniscient benchmark, achieving competitive ratio 0.91, drastically higher than the US status quo policy's 0.51. Our work bridges the gap between data-driven heuristics and pessimistic theoretical lower bounds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。