Improved Online Correlated Selection
Ruiquan Gao, Zhongtian He, Zhiyi Huang, Zipei Nie, Bijun Yuan, Yan Zhong
Abstract
This paper studies online correlated selection (OCS). 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex> rounds, we give an optimal algorithm that minimizes this probability for all k. It leads to 0.536-competitive unweighted and vertex-weighted on-line 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 develop 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 bi-partite matching to get a 0.593-competitive ratio. 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).