12 citations · 22 across the 14 of their papers we have counts for
10 papers · 1 filter
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…
Approximation Algorithms for Action-Reward Query-Commit Matching
Mahsa Derakhshan, Andisheh Ghasemi, Calum MacRury
Matching problems under uncertainty arise in applications such as kidney exchange, hiring, and online marketplaces. A decision-maker must sequentially explore potential matches und…
Stochastic Minimum Vertex Cover in General Graphs: a -Approximation
Mahsa Derakhshan, Naveen Durvasula, Nika Haghtalab
Our main result is designing an algorithm that returns a vertex cover of with size at most times the expected size of the minimum vertex cover, using…
Beating -Approximation for Weighted Stochastic Matching
Mahsa Derakhshan, Alireza Farhadi
In the stochastic weighted matching problem, the goal is to find a large-weight matching of a graph when we are uncertain about the existence of its edges. In particular, each edge…
Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark
Mark Braverman, Mahsa Derakhshan, Antonio Molina Lovett
In this paper, we study max-weight stochastic matchings on online bipartite graphs under both vertex and edge arrivals. We focus on designing polynomial time approximation algorith…
Stochastic Vertex Cover with Few Queries
Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan
We study the minimum vertex cover problem in the following stochastic setting. Let be an arbitrary given graph, a parameter of the problem, and let be a ra…
Stochastic Weighted Matching: Approximation
Soheil Behnezhad, Mahsa Derakhshan
Let be a given edge-weighted graph and let its {\em realization} be a random subgraph of that includes each edge independently with probabili…
Stochastic Matching with Few Queries: Approximation
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi
Suppose that we are given an arbitrary graph and know that each edge in is going to be realized independently with some probability . The goal in the stochastic m…
Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi +2
We present the first algorithm for maintaining a maximal independent set (MIS) of a fully dynamic graph---which undergoes both edge insertions and deletions---in polylogarithmic ti…
Massively Parallel Dynamic Programming on Trees
MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan +2
Dynamic programming is a powerful technique that is, unfortunately, often inherently sequential. That is, there exists no unified method to parallelize algorithms that use dynamic…