2 citations · 5 across the 8 of their papers we have counts for
12 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…
Generalized Stochastic Matching
Alireza Farhadi, Jacob Gilbert, MohammadTaghi Hajiaghayi
In this paper, we generalize the recently studied Stochastic Matching problem to more accurately model a significant medical process, kidney exchange, and several other application…
Online Bipartite Matching with Reusable Resources
Steven Delong, Alireza Farhadi, Rad Niazadeh +2
We study the classic online bipartite matching problem with a twist: offline vertices, called resources, are . In particular, when a resource is matched to an on…
Differentially Private Densest Subgraph
Alireza Farhadi, MohammadTaghi Hajiaghayi, Elaine Shi
Given a graph, the densest subgraph problem asks for a set of vertices such that the average degree among these vertices is maximized. Densest subgraph has numerous applications in…
Almost Envy-freeness, Envy-rank, and Nash Social Welfare Matchings
Alireza Farhadi, MohammadTaghi Hajiaghayi, Mohamad Latifian +2
Envy-free up to one good (EF1) and envy-free up to any good (EFX) are two well-known extensions of envy-freeness for the case of indivisible items. It is shown that EF1 can always…
Asymmetric Streaming Algorithms for Edit Distance and LCS
Alireza Farhadi, MohammadTaghi Hajiaghayi, Aviad Rubinstein +1
The edit distance (ED) and longest common subsequence (LCS) are two fundamental problems which quantify how similar two strings are to one another. In this paper, we consider these…
Approximate Maximum Matching in Random Streams
Alireza Farhadi, MohammadTaghi Hajiaghayi, Tung Mai +2
In this paper, we study the problem of finding a maximum matching in the semi-streaming model when edges arrive in a random order. In the semi-streaming model, an algorithm receive…
Polynomial-time Approximation Scheme for Minimum k-cut in Planar and Minor-free Graphs
MohammadHossein Bateni, Alireza Farhadi, MohammadTaghi Hajiaghayi
The -cut problem asks, given a connected graph and a positive integer , to find a minimum-weight set of edges whose removal splits into connected components. We g…
Stochastic Matching with Few Queries: New Algorithms and Tools
Soheil Behnezhad, Alireza Farhadi, MohammadTaghi Hajiaghayi +1
We consider the following stochastic matching problem on both weighted and unweighted graphs: A graph along with a parameter is given in the input. Each ed…
Lower Bounds for External Memory Integer Sorting via Network Coding
Alireza Farhadi, MohammadTaghi Hajiaghayi, Kasper Green Larsen +1
Sorting extremely large datasets is a frequently occuring task in practice. These datasets are usually much larger than the computer's main memory; thus external memory sorting alg…
On the Complexity of Chore Division
Alireza Farhadi, MohammadTaghi Hajiaghayi
We study the proportional chore division problem where a protocol wants to divide an undesirable object, called chore, among different players. The goal is to find an allocatio…
Fair Allocation of Indivisible Goods to Asymmetric Agents
Alireza Farhadi, Mohammad Ghodsi, MohammadTaghi Hajiaghayi +5
We study fair allocation of indivisible goods to agents with unequal entitlements. Fair allocation has been the subject of many studies in both divisible and indivisible settings.…