5 papers · 1 filter
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…
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…
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…
Query Efficient Weighted Stochastic Matching
Mahsa Derakhshan, Mohammad Saneian
In this paper, we study the weighted stochastic matching problem. Let be a given edge-weighted graph and let its realization be a random subgraph of th…
Streaming Edge Coloring with Asymptotically Optimal Colors
Soheil Behnezhad, Mohammad Saneian
Given a graph , an edge-coloring is an assignment of colors to edges of such that any two edges sharing an endpoint receive different colors. By Vizing's celebrated theorem,…