Online Stochastic Matching with Unknown Arrival Order: Beating $0.5$ against the Online Optimum
By: Enze Sun, Zhihao Gavin Tang, Yifan Wang
Potential Business Impact:
Finds better matches when things arrive randomly.
We study the online stochastic matching problem. Against the offline benchmark, Feldman, Gravin, and Lucier (SODA 2015) designed an optimal $0.5$-competitive algorithm. A recent line of work, initiated by Papadimitriou, Pollner, Saberi, and Wajc (MOR 2024), focuses on designing approximation algorithms against the online optimum. The online benchmark allows positive results surpassing the $0.5$ ratio. In this work, adapting the order-competitive analysis by Ezra, Feldman, Gravin, and Tang (SODA 2023), we design a $0.5+\Omega(1)$ order-competitive algorithm against the online benchmark with unknown arrival order. Our algorithm is significantly different from existing ones, as the known arrival order is crucial to the previous approximation algorithms.
Similar Papers
Combinatorial Philosopher Inequalities
Data Structures and Algorithms
Helps computers share things fairly when people ask.
A New Impossibility Result for Online Bipartite Matching Problems
Data Structures and Algorithms
Finds best ad matches for users faster.
Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model
Machine Learning (CS)
Helps computers make better match-ups with bad guesses.