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/6)-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.


翻译:我们研究的是动态的非双向匹配问题。 有一套固定的代理类型, 特定类型的代理根据特定类型的 Poisson 程序到达和离开。 匹配的价值由匹配的代理商的类型决定。 我们提出了一个在线算法, 相对于最佳近视政策的价值而言具有竞争力(1/6), 对于任意加权图表而言。 这是在抵达和离开都是随机和不通知的情况下实现持续竞争比率的第一个结果。 我们的算法对代理商进行多种不同的处理, 即时和延迟匹配之间的插接, 以便扩大市场, 同时又在机会性上匹配有价值的代理商 。

0
下载
关闭预览

相关内容

【2020新书】Python文本分析,104页pdf
专知会员服务
98+阅读 · 2020年12月23日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【普林斯顿大学-微软】加权元学习,Weighted Meta-Learning
专知会员服务
39+阅读 · 2020年3月25日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
已删除
将门创投
4+阅读 · 2017年11月1日
Arxiv
0+阅读 · 2021年1月18日
Arxiv
0+阅读 · 2021年1月18日
Arxiv
0+阅读 · 2021年1月15日
VIP会员
相关VIP内容
【2020新书】Python文本分析,104页pdf
专知会员服务
98+阅读 · 2020年12月23日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【普林斯顿大学-微软】加权元学习,Weighted Meta-Learning
专知会员服务
39+阅读 · 2020年3月25日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
已删除
将门创投
4+阅读 · 2017年11月1日
Top
微信扫码咨询专知VIP会员