Optimal Online Bipartite Matching in Degree-2 Graphs
A Bhangale, A Chakraborty, P Harsha - arXiv preprint arXiv:2511.16025, 2025 - arxiv.org
A Bhangale, A Chakraborty, P Harsha
arXiv preprint arXiv:2511.16025, 2025•arxiv.orgOnline 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 …
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 …
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 . In this work, we study classes of graphs where the online degree is restricted to . As expected, one can achieve a competitive ratio of better than 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 competitive ratio algorithm is optimal. We show that the folklore \textsc{Half-Half} algorithm achieves a competitive ratio of 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.
arxiv.org