在线随机匹配：基于离线统计的在线决策

我们考虑Feldman等人提出的在线随机匹配问题。Feldman J, Mehta A, Mirrokni VS, Muthukrishnan S（2009）在线随机匹配：超过1 − 1/e。《IEEE年度计算机科学基础会议》117–126，作为展示广告分配的模型。我们给定一个二分图；图的一侧对应于固定的箱子集合，另一侧代表可能的球类型集合。在每个时间步中，从给定分布中独立抽样得到一个球，并且在它到达时需要与一个空箱子匹配。目标是最大化分配的数量。我们提出了一种具有0.702竞争比的在线算法。在我们的结果之前，已知在每种类型的到达球的期望数量是整数的假设下，竞争比优于1 − 1/e的算法。一种关键思路是使用蒙特卡洛抽样收集最佳离线解的决策统计，并使用这些统计数据指导在线算法的决策。我们还展示了当速率为整数时，我们的算法达到了0.705的竞争比。在难度方面，我们证明在已知分布模型下（因此在排列模型下）没有在线算法可以有优于0.823的竞争比。这改进了Goel和Mehta证明的5/6难度结果。Goel G, Mehta A（2008）在线预算匹配在随机输入模型中的应用到广告词。《ACM-SIAM离散算法研讨会》982–991。