用学习建议提升在线二分匹配效率，效果优于随机选择。
Learning-Augmented Online Bipartite Fractional Matching
- 结合学习建议与随机策略，动态调整匹配决策。
- 在顶点加权场景下性能超越经典算法，小额度广告场景提升显著。
- 适用于在线广告、资源分配等实时匹配场景。
在线二分匹配是在线优化中的基础问题，广泛研究于整数和分数形式，具有理论意义与实际应用价值，如在线广告和资源分配。受学习增强算法进展启发，本文研究在每轮迭代中给出建议匹配的在线二分分数匹配问题。针对顶点加权与无权重情形，设计出可严格优于朴素‘抛硬币’策略（即随机选择是否遵循建议）的算法。此外，顶点加权算法在小额度假设下可扩展至AdWords问题，显著优于Mahdian、Nazerzadeh和Saberi（EC 2007, TALG 2012）的经典工作。我们还证明了任何算法在鲁棒性与一致性间的权衡存在固有极限。通过合成与真实数据实验验证了算法有效性。
原文摘要 · Abstract (English)
Online bipartite matching is a fundamental problem in online optimization, extensively studied both in its integral and fractional forms due to its theoretical significance and practical applications, such as online advertising and resource allocation. Motivated by recent progress in learning-augmented algorithms, we study online bipartite fractional matching when the algorithm is given advice in the form of a suggested matching in each iteration. We develop algorithms for both the vertex-weighted and unweighted variants that provably dominate the naive "coin flip" strategy of randomly choosing between the advice-following and advice-free algorithms. Moreover, our algorithm for the vertex-weighted setting extends to the AdWords problem under the small bids assumption, yielding a significant improvement over the seminal work of Mahdian, Nazerzadeh, and Saberi (EC 2007, TALG 2012). Complementing our positive results, we establish a hardness bound on the robustness-consistency tradeoff that is attainable by any algorithm. We empirically validate our algorithms through experiments on synthetic and real-world data.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。