Improved Approximation for Ranking on General Graphs

Mahsa Derakhshan, Mohammad Roghani, Mohammad Saneian, Tao Yu · 2025

Read Improved Approximation for Ranking on General Graphs by Mahsa Derakhshan, Mohammad Roghani, Mohammad Saneian, Tao Yu (2025) 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-2511-06504.txt.

Description

Mahsa Derakhshan, Mohammad Roghani, Mohammad Saneian, and Tao Yu improve the known guarantee of Ranking, a classic randomized matching algorithm, on general graphs. Ranking assigns each vertex a random priority, then matches vertices in that order to the first free neighbor. For bipartite graphs its quality is well mapped, but general graphs resisted tight analysis for decades.

The authors lift the proven approximation ratio from about zero point five two six to zero point five four six nine. Their primal-dual argument introduces the notion of a backup: the partner a vertex would take if its current match vanished. Tracking backups exposes new structure in how ranks distribute across matched pairs.

Catalog record

CREATORMahsa Derakhshan, Mohammad Roghani, Mohammad Saneian, Tao Yu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE127 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-06504

Browse the full library · About the Tower of Babel