Multiway Online Correlated Selection

We give a 0.5368-competitive algorithm for edge-weighted online bipartite matching. Prior to our work, the best competitive ratio was 0.5086 due to Fahrbach, Huang, Tao, and Zadimoghaddam (FOCS 2020). They achieved their breakthrough result by developing a subroutine called online correlated selection (OCS) which takes as input a sequence of pairs and selects one item from each pair. Importantly, the selections the OCS makes are negatively correlated.

We achieve our result by defining multiway OCSes which receive arbitrarily many elements at each step, rather than just two. In addition to better competitive ratios, our formulation allows for a simpler reduction from edge-weighted online bipartite matching to OCSes. While Fahrbach et al. used a factor-revealing linear program to optimize the competitive ratio, our analysis directly connects the competitive ratio to the parameters of the multiway OCS. Finally, we show that the formulation of Farhbach et al. can achieve a competitive ratio of at most 0.5239, confirming that multiway OCSes are strictly more powerful.

in the setting where online vertices are drawn from a known or unknown distribution [FMMM09, KMT11, DJSW19, HMZ11, MGS12, MP12, JL14] or the setting that they arrive in a random order [GM08, DH09, FHK + 10, MY11, MGZ12, MWZ14, HTWZ19]. In addition to these, several recent advances have been made in more general settings including non-bipartite graphs and different arrival models [HKT + 18, GKS19, GKM + 19, HPT + 19].

Consider some weighted bipartite graph G = (L, R, w), where L and R are the left and right vertices respectively. If there is an edge between i ∈ L and j ∈ R, then w ij > 0 is the weight of that edge. Otherwise, w ij = 0.

At the start, the algorithm is given the entire set of left vertices, L, but no information about R or w. The vertices from R appear in an online fashion, one by one. Hence, we refer to L as the offline vertices R as the online vertices. When an online vertex j ∈ R appears, the entries w ij for each i ∈ L are revealed to the algorithm. The algorithm must irrevocably decide which offline vertex to match j to before the next online vertex appears.

The objective is to maximize the total weight of the matching. We operate in the free disposal model. This means a single offline vertex i may be matched to multiple online vertices, but only the weight of its heaviest edge is counted towards the objective. We say a randomized algorithm is "Γ-competitive" or "has competitive ratio of Γ" if the expected objective of the algorithm's output is within a multiplicative factor of Γ of the optimal objective with hindsight.