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.
翻译:我们研究的是动态的非双向匹配问题。 有一套固定的代理类型, 特定类型的代理按照特定类型的 Poisson 程序到达和离开。 代理离开不会提前宣布。 匹配的价值由匹配的代理类型决定。 我们提出了一个在线算法, 相对于最佳内向政策的价值来说, 具有1/8的竞争性, 用于任意的加权图表。 我们的算法以多种方式处理代理, 将即时匹配和延迟匹配相互交错, 以便扩大市场, 同时仍然以机会方式匹配有价值的代理商 。