3 papers
cs.DS2026
A Unified Framework for Analysis of Randomized Greedy Matching Algorithms
Mahsa Derakhshan, Tao Yu
Randomized greedy algorithms form one of the simplest yet most effective approaches for computing approximate matchings in graphs. In this paper, we focus on the class of vertex-it…
cs.DS2025
A Simple Analysis of Ranking in General Graphs
Mahsa Derakhshan, Mohammad Roghani, Mohammad Saneian +1
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 achiev…
cs.DS2025
Improved Approximation for Ranking on General Graphs
Mahsa Derakhshan, Mohammad Roghani, Mohammad Saneian +1
In this paper, we study Ranking, a well-known randomized greedy matching algorithm, for general graphs. The algorithm was originally introduced by Karp, Vazirani, and Vazirani [STO…