论文标题
在线随机匹配中多种选择的力量
The Power of Multiple Choices in Online Stochastic Matching
论文作者
论文摘要
我们研究在线随机匹配中多种选择的力量。尽管进行了长期的研究，但现有算法仍然仅考虑每个在线顶点的离线邻居的两种选择，因为在分析多种选择时面临技术挑战。本文介绍了两种设计和分析使用多种选择的算法的方法。对于未加权且顶点加权的匹配，我们将在线相关选择（OCS）技术采用到随机设置中，并将竞争比率提高到0.716美元，分别从$ 0.711 $和0.7美元。对于免费处置的边缘加权匹配，我们提出了上半部分采样算法。我们通过差异不平等直接表征整个匹配而不是单个顶点的进度。这将竞争比率提高到$ 0.706 $，在文献中首次在此设置中打破了$ 1- \ frac {1} {e} $屏障。最后，对于没有免费处置的硬边缘加权问题，我们证明，没有算法可以是$ 0.703 $竞争性的，将此设置与上述三个分开。
We study the power of multiple choices in online stochastic matching. Despite a long line of research, existing algorithms still only consider two choices of offline neighbors for each online vertex because of the technical challenge in analyzing multiple choices. This paper introduces two approaches for designing and analyzing algorithms that use multiple choices. For unweighted and vertex-weighted matching, we adopt the online correlated selection (OCS) technique into the stochastic setting, and improve the competitive ratios to $0.716$, from $0.711$ and $0.7$ respectively. For edge-weighted matching with free disposal, we propose the Top Half Sampling algorithm. We directly characterize the progress of the whole matching instead of individual vertices, through a differential inequality. This improves the competitive ratio to $0.706$, breaking the $1-\frac{1}{e}$ barrier in this setting for the first time in the literature. Finally, for the harder edge-weighted problem without free disposal, we prove that no algorithms can be $0.703$ competitive, separating this setting from the aforementioned three.
