4 citations · 7 across the 6 of their papers we have counts for
11 papers
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…
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…