We introduce a weighted version of the ranking algorithm by Karp et al. (STOC
1990), and prove a competitive ratio of 0.6534 for the vertex-weighted online
bipartite matching problem when online vertices arrive in random order. Our
result shows that random arrivals help beating the 1-1/e barrier even in the
vertex-weighted case. We build on the randomized primal-dual framework by
Devanur et al. (SODA 2013) and design a two dimensional gain sharing function,
which depends not only on the rank of the offline vertex, but also on the
arrival time of the online vertex. To our knowledge, this is the first
competitive ratio strictly larger than 1-1/e for an online bipartite matching
problem achieved under the randomized primal-dual framework. Our algorithm has
a natural interpretation that offline vertices offer a larger portion of their
weights to the online vertices as time goes by, and each online vertex matches
the neighbor with the highest offer at its arrival.

介绍一种加权排名算法，对于在线顶点以随机顺序到达时的顶点加权二分匹配问题证明了 0.6534 的竞争比率。基于 Devanur 等人的随机原始对偶框架，设计了一个二维收益共享函数来提高算法的竞争比率，并在在线二分匹配问题中达到了大于 1-1 /e 的拓展比率。