论文标题
动态加权匹配与异质到达和出发率
Dynamic Weighted Matching with Heterogeneous Arrival and Departure Rates
论文作者
论文摘要
我们研究一个动态的非双方匹配问题。有一组固定的代理类型，并且给定类型的代理人根据特定于类型的泊松过程到达和离开。代理人出发未提前宣布。匹配的值取决于匹配药物的类型。我们提出了一种在线算法，该算法（1/8）关于任意加权图的最佳视觉策略的价值（1/8）。我们的算法会异质地对待代理，在即时和延迟匹配之间进行插值，以使市场增稠，同时仍然可以机会匹配有价值的代理商。
We study a dynamic non-bipartite matching problem. There is a fixed set of agent types, and agents of a given type arrive and depart according to type-specific Poisson processes. Agent departures are not announced in advance. The value of a match is determined by the types of the matched agents. We present an online algorithm that is (1/8)-competitive with respect to the value of the optimal-in-hindsight policy, for arbitrary weighted graphs. Our algorithm treats agents heterogeneously, interpolating between immediate and delayed matching in order to thicken the market while still matching valuable agents opportunistically.
