4 papers
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…
One-way Communication Complexity of Minimum Vertex Cover in General Graphs
Mahsa Derakhshan, Andisheh Ghasemi, Rajmohan Rajaraman
We study the communication complexity of the Minimum Vertex Cover (MVC) problem on general graphs within the \(k\)-party one-way communication model. Edges of an arbitrary \(n\)-ve…
New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling
Mark Braverman, Mahsa Derakhshan, Tristan Pollner +2
We study the polynomial-time approximability of the optimal online stochastic bipartite matching algorithm, initiated by Papadimitriou et al. (EC'21). Here, nodes on one side of th…