A Simple Analysis of Ranking in General Graphs
arXiv:2511.08801
Abstract
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 -approximate matching for general graphs for .