论文标题
（分数）通过细粒的离线统计数据在线随机匹配
(Fractional) Online Stochastic Matching via Fine-Grained Offline Statistics
论文作者
论文摘要
Feldman，Mehta，Mirrokni和Muthukrishnan提出了在互联网上展示广告的激励，在线随机匹配问题（FOCS 2009）提出了。考虑一个随机的两分图，一侧和I.I.D有离线顶点。另一侧的在线顶点。该算法提前知道离线顶点和在线顶点的分布。每个在线顶点到达后，它的类型就会实现，该算法立即决定如何匹配它。在问题的顶点加权版本中，每个离线顶点都与重量相关联，目标是最大化匹配的总重量。 在本文中，我们将模型概括为允许非相同的在线顶点，并专注于顶点加权随机匹配的分数版本。我们设计的分数算法为$ 0.718 $ - 竞争，$ 0.731 $ - 竞争非i.i.d.到达和I.I.D.到达分别。我们还证明，没有分数算法的竞争比率可以更好地超过$ 0.75 $的$ i.i.d。到达。此外，我们通过应用Gao等人的最近开发的多线在线相关选择来绕过分数算法。 （focs 2021）并获得$ 0.666 $竞争的$竞争和$ 0.704 $ - 竞争性的积分算法，用于非I.I.D.到达和I.I.D.到达。我们针对非i.i.d.的结果到达是第一个算法，击败了经典对抗性设置的$ 1-1/e \ $ 0.632 $障碍。我们的$ 0.704 $竞争性集成算法用于I.I.D.到达略微提高了Huang and Shu（STOC 2021）的最新$ 0.701 $竞争比率。
Motivated by display advertising on the internet, the online stochastic matching problem is proposed by Feldman, Mehta, Mirrokni, and Muthukrishnan (FOCS 2009). Consider a stochastic bipartite graph with offline vertices on one side and with i.i.d. online vertices on the other side. The algorithm knows the offline vertices and the distribution of the online vertices in advance. Upon the arrival of each online vertex, its type is realized and the algorithm immediately and irrevocably decides how to match it. In the vertex-weighted version of the problem, each offline vertex is associated with a weight and the goal is to maximize the total weight of the matching. In this paper, we generalize the model to allow non-identical online vertices and focus on the fractional version of the vertex-weighted stochastic matching. We design fractional algorithms that are $0.718$-competitive and $0.731$-competitive for non i.i.d. arrivals and i.i.d. arrivals respectively. We also prove that no fractional algorithm can achieve a competitive ratio better than $0.75$ for non i.i.d. arrivals. Furthermore, we round our fractional algorithms by applying the recently developed multiway online correlated selection by Gao et al. (FOCS 2021) and achieve $0.666$-competitive and $0.704$-competitive integral algorithms for non i.i.d. arrivals and i.i.d. arrivals. Our results for non i.i.d. arrivals are the first algorithms beating the $1-1/e \approx 0.632$ barrier of the classical adversarial setting. Our $0.704$-competitive integral algorithm for i.i.d. arrivals slightly improves the state-of-the-art $0.701$-competitive ratio by Huang and Shu (STOC 2021).
