A Simple Analysis of Ranking in General Graphs
Mahsa Derakhshan, Mohammad Roghani, Mohammad Saneian, Tao Yu · Society for Industrial and Applied Mathematics eBooks · 2026
We provide a simple combinatorial analysis of the Ranking algorithm, originally introduced in the seminal work by Karp, Vazirani, and Vazirani [KVV90], demonstrating that it achieves a \((1/2+c)\)-approximate matching for general graphs for \(c \ge 0.005\).