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.

Authors

• Guy Blanc
• Moses Charikar

Keywords

• Computer science
• Algorithms
• Negatively Correlated
• Matching Algorithm
• Competitive Ratio
• Time Step
• Upper Bound
• Marginal Distribution
• Metaheuristic
• Tournament
• Probability Vector
• Competitive Algorithm
• Online Fashion
• Input Instance
• Win Probability
• Perfect Negative Correlation
• online algorithms
• online matching
• online correlated selection