论文标题
完全在线匹配II：殴打排名和填充水
Fully Online Matching II: Beating Ranking and Water-filling
论文作者
论文摘要
Karp，Vazirani和Vazirani（Stoc 1990）开始了对在线两部分匹配的研究，从那以后，该匹配在线算法中扮演着核心角色。尤其重要的是积分匹配的排名算法和分数匹配的水填充算法。文献中的大多数算法都可以看作是相应模型中这两者的适应。最近，Huang等人（STOC 2018，SODA 2019）推出了一个更通用的模型，称为\ emph {完全在线匹配}，该模型考虑了一般图，并允许所有顶点在线到达。他们还将全面的排名和填充水加入到完全在线匹配，并进行了一些严格的分析：在两部分图上，排名为$ω\约0.567 $ - 竞争，其中$ω$ -Constant满足$ωe^ω= 1 $，并且水的填充为$ 2- \ sqrt $ 2- \ sqrt oon {2} \ of tragral oon Gressive of Brapentive of Grance of Grange of Grange of Grange of Grange of Grange of Bragption of Gragress \ -comcpetsive-comcpetsive-comcpetsive-comcpet。 我们建议完全在线匹配算法比排名和填充水。对于在两部分图上进行的整体匹配，我们基于在线原始双重分析和填充水，以设计一种$ 0.569 $竞争的混合算法，称为均衡排名。据我们所知，这是在线匹配文献中第一个不可或缺的算法，成功地整合了水上填充思想的想法。对于一般图表上的分数匹配，我们提供了一种$ 0.592 $竞争性的算法，称为急切的水填充物，该算法可能与顶点到达时可能匹配。相比之下，原始的填充算法总是与他们的最后期限相匹配。我们对分数匹配的结果进一步显示了Wang and Wong（ICALP 2015）的完全在线匹配与一般顶点到达模型之间的分离，这是由于Buchbinder，Segev和Tkach的后一种型号的上限为0.5914美元，而Tkach（ESA 2017）。
Karp, Vazirani, and Vazirani (STOC 1990) initiated the study of online bipartite matching, which has held a central role in online algorithms ever since. Of particular importance are the Ranking algorithm for integral matching and the Water-filling algorithm for fractional matching. Most algorithms in the literature can be viewed as adaptations of these two in the corresponding models. Recently, Huang et al.~(STOC 2018, SODA 2019) introduced a more general model called \emph{fully online matching}, which considers general graphs and allows all vertices to arrive online. They also generalized Ranking and Water-filling to fully online matching and gave some tight analysis: Ranking is $Ω\approx 0.567$-competitive on bipartite graphs where the $Ω$-constant satisfies $Ωe^Ω= 1$, and Water-filling is $2-\sqrt{2} \approx 0.585$-competitive on general graphs. We propose fully online matching algorithms strictly better than Ranking and Water-filling. For integral matching on bipartite graphs, we build on the online primal dual analysis of Ranking and Water-filling to design a $0.569$-competitive hybrid algorithm called Balanced Ranking. To our knowledge, it is the first integral algorithm in the online matching literature that successfully integrates ideas from Water-filling. For fractional matching on general graphs, we give a $0.592$-competitive algorithm called Eager Water-filling, which may match a vertex on its arrival. By contrast, the original Water-filling algorithm always matches vertices at their deadlines. Our result for fractional matching further shows a separation between fully online matching and the general vertex arrival model by Wang and Wong (ICALP 2015), due to an upper bound of $0.5914$ in the latter model by Buchbinder, Segev, and Tkach (ESA 2017).
