2 citations · 5 across the 8 of their papers we have counts for
8 papers · 1 filter
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…
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…