论文标题
改善了分数在线匹配问题的界限
Improved Bounds for Fractional Online Matching Problems
论文作者
论文摘要
自KARP，Vazirani和Vazirani开创性的工作以来，在线双方与单方面到达及其变体进行了广泛的研究（Stoc 1990）。由具有动态市场结构的现实应用程序的动机，例如提出了乘车共享，两种经典单方面到达模型的概括，以允许非双向图，并允许所有顶点在线到达。也就是说，Wang and Wong（ICALP 2015）引入了与General Vertex到达的在线匹配，Huang等人介绍了完全在线匹配。 （JACM 2020）。 在本文中，我们研究了两个模型的分数版本。在这两个模型的四个最新上限和下限中，我们改善了三个。对于完全在线匹配，我们设计了$ 0.6 $竞争的算法，并且证明没有算法为$ 0.613 $竞争。对于与General Vertex到达的在线匹配，我们证明没有算法可以是$ 0.584 $竞争。此外，与Wang和Wong的算法相比，我们可以说，对于一般顶点到达模型，我们可以说出一种更直观的算法，同时获得了相同的竞争比率为0.526美元。
Online bipartite matching with one-sided arrival and its variants have been extensively studied since the seminal work of Karp, Vazirani, and Vazirani (STOC 1990). Motivated by real-life applications with dynamic market structures, e.g. ride-sharing, two generalizations of the classical one-sided arrival model are proposed to allow non-bipartite graphs and to allow all vertices to arrive online. Namely, online matching with general vertex arrival is introduced by Wang and Wong (ICALP 2015), and fully online matching is introduced by Huang et al. (JACM 2020). In this paper, we study the fractional versions of the two models. We improve three out of the four state-of-the-art upper and lower bounds of the two models. For fully online matching, we design a $0.6$-competitive algorithm and prove no algorithm can be $0.613$-competitive. For online matching with general vertex arrival, we prove no algorithm can be $0.584$-competitive. Moreover, we give an arguably more intuitive algorithm for the general vertex arrival model, compared to the algorithm of Wang and Wong, while attaining the same competitive ratio of $0.526$.
