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

oai:drops-oai.dagstuhl.de:24921 2026-09-23T23:21:11Z ddc:004 open_access

Optimal Online Bipartite Matching in Degree-2 Graphs Bhangale, Amey Chakraborty, Arghya Harsha, Prahladh Online Algorithm Bipartite matching Online bipartite matching is a classical problem in online algorithms and we know that both the deterministic fractional and randomized integral online matchings achieve the same competitive ratio of 1-1/e. In this work, we study classes of graphs where the online degree is restricted to 2. As expected, one can achieve a competitive ratio of better than 1-1/e in both the deterministic fractional and randomized integral cases, but surprisingly, these ratios are not the same. It was already known that for fractional matching, a 0.75 competitive ratio algorithm is optimal. We show that the folklore Half-Half algorithm achieves a competitive ratio of η ≈ 0.717772… and more surprisingly, show that this is optimal by giving a matching lower-bound. This yields a separation between the two problems: deterministic fractional and randomized integral, showing that it is impossible to obtain a perfect rounding scheme. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amey Bhangale and Arghya Chakraborty and Prahladh Harsha 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.13 urn:nbn:de:0030-drops-249216 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.13 eng https://creativecommons.org/licenses/by/4.0/legalcode