8 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…
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…