mlsanityData to 14 Oct 2026

A Simple Analysis of Ranking in General Graphs

arXiv 2511.08801 ↗First posted 11 Nov 2025cs.DScited by 1

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Stochastic Matching via Local Sparsificationcited by 0