Dynamic Weighted Matching with Heterogeneous Arrival and Departure Rates
Dynamic Weighted Matching with Heterogeneous Arrival and Departure Rates
复制标题
具有异构到达率和出发率的动态加权匹配
DOI：
10.1007/978-3-030-64946-3_2
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Newman, Neil
中科院分区：
文献类型：
--
作者：
Collina, Natalie;Immorlica, Nicole;Leyton-Brown, Kevin;Lucier, Brendan;Newman, Neil
研究了一个动态的非二部匹配问题。存在一组固定的代理类型，给定类型的代理根据特定类型的泊松过程到达和离开。匹配的值由匹配的代理的类型决定。我们提出了一种在线算法，对于任意加权图，它与事后最优策略的值（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. 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. This is the first result to achieve a constant competitive ratio when both arrivals and departures are random and unannounced. Our algorithm treats agents heterogeneously, interpolating between immediate and delayed matching in order to thicken the market while still matching valuable agents opportunistically.
登录
查看更多内容
DOI：
10.1287/opre.2017.1644
发表时间：
2017-09
期刊：
Oper. Res.
影响因子：
--
作者：
Ross Anderson;I. Ashlagi;D. Gamarnik;Yashodhan Kanoria
通讯作者：
Ross Anderson;I. Ashlagi;D. Gamarnik;Yashodhan Kanoria
DOI：
10.1137/1.9781611974331.ch72
发表时间：
2015-08
期刊：
--
影响因子：
--
作者：
Moran Feldman;O. Svensson;R. Zenklusen
通讯作者：
Moran Feldman;O. Svensson;R. Zenklusen
DOI：
--
发表时间：
2018-07
期刊：
--
影响因子：
--
作者：
John P. Dickerson;Karthik Abinav Sankararaman;A. Srinivasan;Pan Xu
通讯作者：
John P. Dickerson;Karthik Abinav Sankararaman;A. Srinivasan;Pan Xu
最优动态匹配
DOI：
10.2139/ssrn.2641670
发表时间：
2015
期刊：
ERN: Search
影响因子：
--
作者：
Mariagiovanna Baccara;SangMok Lee;Leeat Yariv
通讯作者：
Leeat Yariv
DOI：
10.2139/ssrn.3067596
发表时间：
2016
期刊：
Proceedings of the 2016 ACM Conference on Economics and Computation
影响因子：
--
作者：
I. Ashlagi;Maximilien Burq;Patrick Jaillet;V. Manshadi
通讯作者：
V. Manshadi