论文标题
改进了以随机顺序模型的在线顶点加权两部分匹配的排名分析
Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching in the Random Order Model
论文作者
论文摘要
在本文中，我们考虑了随机到达模型中的在线顶点加权二手匹配问题。我们考虑了Huang，Tang，Wu和Zhang引入的此问题的排名算法的概括（Talg 2019），他们表明他们的算法的竞争比率为0.6534。我们表明，他们的分析中的假设可以削弱，从而通过线性程序来替换单位正方形上关键函数$ g $的推导，该线性程序在这些假设下以离散的单位平方计算这些假设的最佳$ g $值。我们表明，离散化不会引起太多错误，并在计算上表明我们可以获得0.6629的竞争比率。为了计算离散的单位正方形上的界限，我们使用并行化，并且仍然需要在64核机上进行两天的计算。此外，通过在某种程度上修改线性程序，我们可以在计算上显示在0.6688的方法上的上限；超出该约束的任何进一步进展都需要在$ g $的假设中进一步削弱，或者比Huang等人的分析更强大。
In this paper, we consider the online vertex-weighted bipartite matching problem in the random arrival model. We consider the generalization of the RANKING algorithm for this problem introduced by Huang, Tang, Wu, and Zhang (TALG 2019), who show that their algorithm has a competitive ratio of 0.6534. We show that assumptions in their analysis can be weakened, allowing us to replace their derivation of a crucial function $g$ on the unit square with a linear program that computes the values of a best possible $g$ under these assumptions on a discretized unit square. We show that the discretization does not incur much error, and show computationally that we can obtain a competitive ratio of 0.6629. To compute the bound over our discretized unit square we use parallelization, and still needed two days of computing on a 64-core machine. Furthermore, by modifying our linear program somewhat, we can show computationally an upper bound on our approach of 0.6688; any further progress beyond this bound will require either further weakening in the assumptions of $g$ or a stronger analysis than that of Huang et al.
