Improved Online Correlated Selection

This paper studies the online correlated selection (OCS) problem. It was introduced by Fahrbach, Huang, Tao, and Zadimoghaddam (2020) to obtain 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 immediately 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 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 bipartite matching and is 0.593-competitive. Finally, we study OCS, which further considers the probability that an element is unselected in an arbitrary 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.

• This is the second version on arXiv. Compared to the first version, this one adds a discussion on two concurrent works on the same topic, gives a more accurate description of previous results, and improves the presentation based on the feedbacks by anonymous reviewers. The conference version appears in FOCS 2021.