12 citations · 22 across the 14 of their papers we have counts for
19 papers
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…
Multi-Agent Reinforcement Learning Counteracts Delayed CSI in Multi-Satellite Systems
Marios Aristodemou, Yasaman Omid, Sangarapillai Lambotharan +2
The integration of satellite communication networks with next-generation (NG) technologies is a promising approach towards global connectivity. However, the quality of services is…
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…
Learning and Collusion in Multi-unit Auctions
Simina Brânzei, Mahsa Derakhshan, Negin Golrezaei +1
We consider repeated multi-unit auctions with uniform pricing, which are widely used in practice for allocating goods such as carbon licenses. In each round, identical units of…
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…
Beating Greedy For Approximating Reserve Prices in Multi-Unit VCG Auctions
Mahsa Derakhshan, David M. Pennock, Aleksandrs Slivkins
We study the problem of finding personalized reserve prices for unit-demand buyers in multi-unit eager VCG auctions with correlated buyers. The input to this problem is a dataset o…
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…
LP-based Approximation for Personalized Reserve Prices
Mahsa Derakhshan, Negin Golrezaei, Renato Paes Leme
We study the problem of computing data-driven personalized reserve prices in eager second price auctions without having any assumption on valuation distributions. Here, the input i…
Optimal Strategies of Blotto Games: Beyond Convexity
Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan +3
The Colonel Blotto game, first introduced by Borel in 1921, is a well-studied game theory classic. Two colonels each have a pool of troops that they divide simultaneously among a s…
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…
Massively Parallel Symmetry Breaking on Sparse Graphs: MIS and Maximal Matching
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi +1
The success of modern parallel paradigms such as MapReduce, Hadoop, or Spark, has attracted a significant attention to the Massively Parallel Computation (MPC) model over the past…
Semi-MapReduce Meets Congested Clique
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi
Graph problems are troublesome when it comes to MapReduce. Typically, to be able to design algorithms that make use of the advantages of MapReduce, assumptions beyond what the mode…
A Polynomial Time Algorithm for Spatio-Temporal Security Games
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi +1
An ever-important issue is protecting infrastructure and other valuable targets from a range of threats from vandalism to theft to piracy to terrorism. The "defender" can rarely af…
Faster and Simpler Algorithm for Optimal Strategies of Blotto Game
Soheil Behnezhad, Sina Dehghani, Mahsa Derakhshan +2
In the Colonel Blotto game, which was initially introduced by Borel in 1921, two colonels simultaneously distribute their troops across different battlefields. The winner of each b…