A Simple Analysis of Ranking in General Graphs

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\mathrm{/}2+c)$-approximate matching for general graphs for $c\ge 0.005$.