Beta在线匹配

摘要

二部图的在线匹配问题最早由Karp等人在1990年提出,该问题在近年得到了广泛的关注,在日常生活中有大量的应用.本文引入了Beta分布作为二部图节点间的邻接关系的统计先验,提出了最大化节点的预留匹配能力准则作为在线匹配策略的评价度量,设计了在线匹配算法BetaOM,并证明了该算法的正确性.本文把BetaOM分别应用于基于人造数据和真实数据的在线匹配问题,实验的结果显示该算法优于经典的Greedy算法和Ranking算法.%In recent years,the online bipartite graph matching problem has attracted substantial research attention as many real-life problems can be eventually reduced to it.In this work,we study the classic online matching problem that was initially investigated by Karp in 1990.We adopt the Beta distribution as the prior distribution of the adjacency relation among the nodes,and present a novel measure to evaluate the matching policy.We also design BetaOM,a Beta distribution based online matching algorithm,and mathematically prove its soundness.Experiments with BetaOM as well as the benchmark algorithms on both synthetic and real data demonstrate that the proposed BetaOM is superior to the others.