A Simple Analysis of Ranking in General Graphs
Mahsa Derakhshan, Mohammad Roghani, Mohammad Saneian, Tao Yu
我们提供了对排名算法的简单组合分析,最初由Karp,Vazirani和Vazirani [KVV90]在开创性工作中引入,证明它实现了c≥0.005的一般图形的(1/2 + c)近似匹配。
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.
