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
| CREATOR | Mahsa Derakhshan, Mohammad Roghani, Mohammad Saneian, Tao Yu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 127 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-06504