# A Simple Analysis of Ranking in General Graphs

arXiv: https://arxiv.org/abs/2511.08801 · HTML: https://mlsanity.com/paper/2511.08801/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Nov 2025.

## Built on by (most cited first, 1 of 1)

- [Stochastic Matching via Local Sparsification](https://mlsanity.com/paper/2605.14195/) (2026)

## Abstract (arXiv)

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 ≥ 0.005.