具有截止时间实例的快速高效匹配算法

May, 2023

具有截止时间实例的快速高效匹配算法

Fast and Efficient Matching Algorithm with Deadline Instances

Zhao Song, Weixin Wang, Chenbo Yin

TL;DR介绍一种具有截止时间使用市场模型的在线加权匹配问题算法，并使用 FastGreedy 和 FastPostponedGreedy 算法来获得更好的时间复杂度和更高的竞争比。

Abstract

online weighted matching problem is a fundamental problem in machine learning due to its numerous applications. Despite many efforts in this area, existing algorithms are either too slow or don't take $\mathrm{deadline}$ (the longest time a node can be matched) into account. In this pa

online weighted matching problem market model fastgreedy fastpostponedgreedy time complexity

发现论文，激发创造

带期限的最大权重在线匹配

研究匹配到一个时间市场上的代理人的问题，该论文提出了不同的算法来解决顺序不同的场景，并在独立抽样的时间场景中实现 1/8-competitive 算法，对于随机顺序情况下提出了一个每 (d+1) 阶段计算最大加权匹配的 batching 算法，并且证明了其 0.279-competitive 的竞争性。

Aug, 2018

随机匹配问题的改进近似算法

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

May, 2015

大规模图匹配的快速投影固定点算法

本论文提出了一种快速的大型图匹配的近似算法，使用新的投影固定点方法和双向随机投影的方法实现算法，理论上保证收敛速度为线性，并在大型合成和真实图上进行了广泛的实验，与之前的算法相比，在速度和准确性方面都有更好的表现。

Jul, 2012

面向带客户偏好的服务在线提前预定调度

本文研究预约服务的 Web 和移动应用程序，针对该类问题提出了带性能保证的新算法，并在纽约市卫生系统的预约数据上进行了测试。

May, 2018

在线随机匹配：新算法和界限

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