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

CREATORKanstantsin Pashkovich, Thomas Snow
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE124 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-07355

Browse the full library · About the Tower of Babel