2025/11/11 by Mahsa Derakhshan, Derakhshan, Mahsa, Mohammad Roghani +5
Computer Science · Economics, Econometrics and Finance · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2511.08801
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.