Edge-weighted Online Stochastic Matching Under Jaillet-Lu LP
For researchers in online algorithms, this work provides tight bounds for a decade-old problem, indicating the limits of current LP-based approaches.
The paper tightens the competitive ratio for edge-weighted online stochastic matching under the Jaillet-Lu LP to between 0.662 and 0.663, showing that further improvement beyond 0.001 requires more powerful LPs or multiple-choice strategies.
The online stochastic matching problem was introduced by [FMMM09], together with the $(1-\frac1e)$-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-\frac1e$ bound and [QFZW23] further improved it to $0.650$. Both works measure the online competitiveness against the offline LP relaxation introduced by Jaillet and Lu [JL14]. The same LP has also played an important role in other settings as it is a natural choice for two-choice online algorithms. In this paper, we prove an upper bound of $0.663$ and a lower bound of $0.662$ for edge-weighted online stochastic matching under Jaillet-Lu LP. We propose a simple hard instance and identify the optimal online algorithm for this specific instance which has a competitive ratio of $<0.663$. Despite the simplicity of the instance, we then show that a near-optimal algorithm for it, which has a competitive ratio of $>0.662$, can be generalized to work on all instances without any loss. As our algorithm is generalized from a real near-optimal algorithm instead of manually combining trivial strategies, it has two natural advantages compared with previous works: (1) its matching strategy varies from time to time; (2) it utilizes global information about offline vertices. On the other hand, the upper bound suggests that more powerful LPs and multiple-choice strategies are needed if we want to further improve the ratio by $>0.001$. In addition to our main result, we also generalize the asymptotic equivalence between the Poisson arrival model and the original online stochastic matching established by [HS21], removing the requirement of approximate monotonicity for the online algorithm.