2026-10-01T23:07:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26545 2026-09-24T00:10:08Z ddc:004 open_access

Edge-Weighted Online Stochastic Matching Under Jaillet-Lu LP Yan, Shuyi Online stochastic matching The online stochastic matching problem was introduced by [Feldman et al., 2009], together with the (1-1/e)-competitive Suggested Matching algorithm. In the most general edge-weighted setting, this ratio has not been improved for more than one decade, until recently [Yan, 2024] beat the 1-1/e bound and [Qiu et al., 2023] further improved it to 0.650. Both works measure the online competitiveness against the offline LP relaxation introduced by Jaillet and Lu [Jaillet and Lu, 2014]. 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 [Huang and Shu, 2021], removing the requirement of approximate monotonicity for the online algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shuyi Yan 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.156 urn:nbn:de:0030-drops-265450 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.156 eng https://creativecommons.org/licenses/by/4.0/legalcode