本文在研究用稳定匹配问题的原型模型，在不同的图形情况下，稳定匹配问题的难易程度， 并提出了五个猜想来描述随机稳定匹配的渐近特性。

Sep, 2005

本研究针对多阶段组合优化问题中的贪心近似方法，通过研究维护基数和最佳匹配的多阶段马氏处理问题，提出了一种时间复杂度为 $O (log (m) log (r))$ 的近似算法，并在离线情况下给出时间复杂度为 $O (log (m))$ 的近似算法，但当 acquisition costs 不均匀时，我们 的算法是最优的，并证明即使在完美匹配的情况下，该问题的近似难度也很大。

Apr, 2014

本研究介绍了一种算法来解决在线随机二分匹配问题，提供了一个 0.67 的逼近比和一种基于流量图和最大流问题的新方法来解决这个问题。

May, 2009

研究在线随机匹配问题，提出了基于 Poisson 到达模型的 0.711 竞争性算法和近似等价性证明，应用线性规划和 Jensen 不等式实现算法优化，推出第一个在较弱随机到达模型下的节点加权在线随机匹配算法。

Mar, 2021

本文提出了一些基本的算法变体和改进，旨在提高已知 IID 模型和具有随机奖励延伸的模型的竞争比率，另外提出了加强型线性规划基准来提高非加权边的概率的情况。

Jun, 2016

本文研究了随机匹配问题，提出一种能够提高精度的探测边的新方法和其在最大化构建匹配的期望收益中的应用，尤其在求解在线偏二分图情况时取得了显著提升。

May, 2015

本研究探讨了稳定匹配问题中鲁棒性的概念，定义了（a，b）- 超级匹配，并将最鲁棒的稳定匹配定义为（1，b）- 超级匹配，我们用多项式时间检查给定的稳定匹配是否为（1，b）- 超级匹配，然后设计了约束编程模型、局部搜索方法和遗传算法以找到最鲁棒的稳定匹配，实验证明局部搜索优于其他方法。

May, 2017

本论文提出一种基于 Monte Carlo 采样的在线算法，在解决传播广告分配问题的同时，实现 competing ratio 为 0.702，也证明了当到达速率为整数时 competing ratio 为 0.705。同时，我们还证明采用已知分布模型无法实现 competing ratio 小于 0.823。

Jul, 2010

本文介绍了半在线模型，分析了其应用于二分图匹配问题的效果，给出了竞争性的算法并证明其同样具有竞争性，竞争度可以在完全在线模型和完全离线模型之间插值。

Dec, 2018

研究在线非加权二分图匹配中的问题，其中有 n 个离线顶点和 n 个在线顶点，并且希望与最佳离线算法保持竞争力。尽管 Karp 等人 [1990] 的经典 RANKING 算法可以证明达到 1-1/e>1/2 的竞争比率，但我们表明在对抗性到达模型中，没有学习增强方法既可以是 1 - 一致的又可以比 1/2 - 健壮。同时，在随机到达模型下，我们展示了如何利用分布测试方法设计出一种算法，该算法接受关于在线顶点的外部建议，并在竞争比率上从不需要建议的方法和最优比率 1 之间插值，这取决于建议的质量。

May, 2024