Online bipartite matching is a classical problem in online algorithms and we know that both the deterministic fractional and randomized integral online matchings achieve the same competitive ratio of $1-\frac{1}{e}$. In this work, we study classes of graphs where the online degree is restricted to $2$. As expected, one can achieve a competitive ratio of better than $1-\frac{1}{e}$ in both the deterministic fractional and randomized integral cases, but surprisingly, these ratios are not the same. It was already known that for fractional matching, a $0.75$ competitive ratio algorithm is optimal. We show that the folklore \textsc{Half-Half} algorithm achieves a competitive ratio of $η\approx 0.717772\dots$ and more surprisingly, show that this is optimal by giving a matching lower-bound. This yields a separation between the two problems: deterministic fractional and randomized integral, showing that it is impossible to obtain a perfect rounding scheme.
翻译：在线二分图匹配是在线算法中的一个经典问题，已知确定性分数匹配和随机化整数在线匹配均能达到 $1-\\frac{1}{e}$ 的竞争比。本文研究在线度数限制为 $2$ 的图类。正如预期，在确定性分数匹配和随机化整数匹配两种情况下，均可获得优于 $1-\\frac{1}{e}$ 的竞争比；但令人惊讶的是，两者的最优竞争比并不相同。已有研究表明，对于分数匹配，$0.75$ 竞争比算法是最优的。我们证明经典的 \\textsc{Half-Half} 算法能达到约 $η≈0.717772\\dots$ 的竞争比，并进一步通过给出匹配的下界证明该结果是最优的。这揭示了确定性分数匹配与随机化整数匹配问题之间的分离性，表明无法实现完美的舍入方案。
相关内容
微信扫码咨询专知VIP会员