This analysis proposes upper and lower bounds of 0.663 and 0.662 for online stochastic matching, indicating the need for stronger LPs.
The online stochastic matching problem was introduced by [FMMM09], together with the (1-1e)-competitive Suggested Matching algorithm. In the most general edge-weighted setting, this ratio has not been improved for more than one decade, until recently [Yan24] beat the 1-1e bound and [QFZW23] further improved the ratio to $0.650$. Both of these works measure the online competitiveness against the offline LP relaxation introduced by [JL14]. This LP has also played an important role in other settings since it is a natural choice for two-choices online algorithms. In this paper, we propose an upper bound of $0.663$ and a lower bound of $0.662$ for edge-weighted online stochastic matching under Jaillet-Lu LP. First, we propose a hard instance and prove that the optimal online algorithm for this instance only has a competitive ratio $<0.663$. Then, we show that a near-optimal algorithm for this instance can be generalized to work on all instances and achieve a competitive ratio $>0.662$. It indicates that more powerful LPs are necessary if we want to further improve the ratio by $0.001$.
No takes yet. Share an insight, caveat, or question.
Shuyi Yan (2025) studied this question.