This paper studies the online correlated selection (OCS) problem introduced by Fahrbach, Huang, Tao, and Zadimoghaddam (2020) to get the first edge-weighted online bipartite matching algorithm that breaks the $0.5$ barrier. Suppose that we receive a pair of elements in each round and select one of them. Can we select with negative correlation to be more effective than independent random selections? Our contributions are threefold. For semi-OCS, which considers the probability that an element remains unselected after appearing in $k$ rounds, we give an optimal algorithm that minimizes this probability for all $k$. It leads to $0.536$-competitive unweighted and vertex-weighted online bipartite matching algorithms that randomize over only two options in each round, improving the previous 0.508-competitive ratio by Fahrbach et al. (2020). Further, we give the first multi-way semi-OCS that allows an arbitrary number of elements with arbitrary masses in each round. As an application, it rounds the Balance algorithm in unweighted and vertex-weighted online bipartite matching to get a $0.593$-competitive ratio. This is the first algorithm other than Ranking whose competitive ratio is beyond the $0.5 + \epsilon$ regime. Finally, we study OCS, which further considers the probability that an element is unselected in any subset of rounds. We prove that the optimal "level of negative correlation" is between $0.167$ and $0.25$, improving the previous bounds of $0.109$ and $1$ by Fahrbach et al. (2020). Our OCS gives a $0.519$-competitive edge-weighted online bipartite matching algorithm, improving the previous $0.508$-competitive ratio by Fahrbach et al. (2020).

翻译：本文研究Fahrbach、 Huang、 Tao 和 Zadimoghaddam (202020年) 推出的在线相关选择(OCS) 问题, 以获得第一个突破0. 5美元屏障的超标在线双边匹配算法。 假设我们每轮只收到一对元素, 并选择其中之一。 我们能否以负相关选择方式选择比独立随机选择更有效? 我们的贡献是三倍。 对于半OCS来说, 半OCS 认为一个元素在以美元计价后仍未被选中的可能性, 我们给出了一种最佳算法, 将所有美元比值的比值降到最低。 它导致536美元有竞争力的在线双边比值( 未加权和顶值) 5美元比值的在线双边匹配。 最后, Fahrbach 和 al. (202020年) 之前的508 竞争比值比值比值比值增加0. 。 我们的上一个多半OCSS, 通过一个应用, 将平衡算法值比值比值的比值比值比值比值比值比值比值比值比值比值比值比值比值比值的O 0.20505, 我们的比值比值比值前的O