{"ID":2838893,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.16025","arxiv_id":"2511.16025","title":"Optimal Online Bipartite Matching in Degree-2 Graphs","abstract":"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-\\frac{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-\\frac{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 \\textsc{Half-Half} algorithm achieves a competitive ratio of $η\\approx 0.717772\\dots$ 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.","short_abstract":"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-\\frac{1}{e}$. In this work, we study classes of graphs where the online degree is restricted to $2$. As expected, one...","url_abs":"https://arxiv.org/abs/2511.16025","url_pdf":"https://arxiv.org/pdf/2511.16025v1","authors":"[\"Amey Bhangale\",\"Arghya Chakraborty\",\"Prahladh Harsha\"]","published":"2025-11-20T04:12:49Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}