3 papers
cs.DS2026
Half-Approximating Maximum Dicut in the Streaming Setting
Amir Azarmehr, Soheil Behnezhad, Shane Ferrante +1
We study streaming algorithms for the maximum directed cut problem. The edges of an -vertex directed graph arrive one by one in an arbitrary order, and the goal is to estimate t…
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…