DISPATCH: An Optimally-Competitive Algorithm for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals
DISPATCH: An Optimally-Competitive Algorithm for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals
复制标题
DISPATCH：一种用于最大在线完美二分匹配的最优竞争算法
DOI：
10.1007/978-3-030-04693-4_10
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Chang Minjun, Hochbaum Dorit
中科院分区：
文献类型：
--
作者：
Chang Minjun, Hochbaum Dorit
本文提出了一种最优竞争算法来解决带独立同分布到达的最大加权在线完美二部匹配问题。在这个问题中，我们给出了一组已知的工人，一个分布在工作类型，和非负的效用权重为每对工人和工作类型。在每个时间步，从作业类型的分布中提取一个作业。到达后，必须将作业合理地分配给工人，并且不能放弃。我们的目标是最大化的期望总和后，所有的工作分配。我们介绍了调度，0.5竞争，随机算法。我们还证明了0.5-competitive是最好的。Dispatchfirst选择一个“首选工人”，并将工作分配给这个工人，如果它是可用的。优选的工人基于分数运输问题的最优解来确定。如果首选工人不可用，Dispatch会从可用工人中随机选择一名工人。我们表明，调度保持均匀分布的工人，即使在工作类型的分布是不均匀的。
This work presents an optimally-competitive algorithm for the problem of maximum weighted online perfect bipartite matching with i.i.d. arrivals. In this problem, we are given a known set of workers, a distribution over job types, and non-negative utility weights for each pair of worker and job types. At each time step, a job is drawn i.i.d. from the distribution over job types. Upon arrival, the job must be irrevocably assigned to a worker and cannot be dropped. The goal is to maximize the expected sum of utilities after all jobs are assigned.We introduceDispatch, a 0.5-competitive, randomized algorithm. We also prove that 0.5-competitive is the best possible.Dispatchfirst selects a “preferred worker” and assigns the job to this worker if it is available. The preferred worker is determined based on an optimal solution to a fractional transportation problem. If the preferred worker is not available,Dispatchrandomly selects a worker from the available workers. We show thatDispatchmaintains a uniform distribution over the workers even when the distribution over the job types is non-uniform.
一种稳健且最优的最小度量二分匹配在线算法
DOI：
10.4230/lipics.approx-random.2016.18
发表时间：
2016
期刊：
The Annals of Probability
影响因子：
--
作者：
S. Raghvendra
通讯作者：
S. Raghvendra
针对随机客户群发布的价格机制
DOI：
10.1145/3033274.3085137
发表时间：
2017
期刊：
Proceedings of the 2017 ACM Conference on Economics and Computation
影响因子：
--
作者：
J. Correa;Patricio Foncea;R. Hoeksma;Tim Oosterwijk;T. Vredeveld
通讯作者：
T. Vredeveld