Online Algorithm for Fractional Matchings with Edge Arrivals in Graphs of Maximum Degree Three
Kanstantsin Pashkovich, Thomas Snow · 2026
Read Online Algorithm for Fractional Matchings with Edge Arrivals in Graphs of Maximum Degree Three by Kanstantsin Pashkovich, Thomas Snow (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-07355.txt.
Description
Online matching with edges arriving one by one is a classic problem. Degree three is where the best possible ratio was known but not known to be achievable. Kanstantsin Pashkovich and one co-author close that gap for fractional matchings.
They supply an online method whose competitive ratio reaches the known upper bound of about 0. 5914 for graphs of maximum degree three, complementing the earlier impossibility result. They also show no online method for integral matchings can reach the same standard. Algorithm builders get a tight result: the bound is not just a barrier but a target that can be hit.
Catalog record
| CREATOR | Kanstantsin Pashkovich, Thomas Snow |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 124 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-07355