65 citations · 195 across the 64 of their papers we have counts for
7 papers · 1 filter
Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein +2
As massive graphs become more prevalent, there is a rapidly growing need for scalable algorithms that solve classical graph problems, such as maximum matching and minimum vertex co…
Simple Round Compression for Parallel Vertex Cover
Sepehr Assadi
Recently, Czumaj et.al. (arXiv 2017) presented a parallel (almost) -approximation algorithm for the maximum matching problem in only rounds of the massive…
Randomized Composable Coresets for Matching and Vertex Cover
Sepehr Assadi, Sanjeev Khanna
A common approach for designing scalable algorithms for massive data sets is to distribute the computation across, say , machines and process the data using limited communicatio…
The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm
Sepehr Assadi, Sanjeev Khanna, Yang Li
In the stochastic matching problem, we are given a general (not necessarily bipartite) graph , where each edge in is realized with some constant probability and…
Combinatorial Auctions Do Need Modest Interaction
Sepehr Assadi
We study the necessity of interaction for obtaining efficient allocations in subadditive combinatorial auctions. This problem was originally introduced by Dobzinski, Nisan, and Ore…
Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem
Sepehr Assadi
We study the classic set cover problem in the streaming model: the sets that comprise the instance are revealed one by one in a stream and the goal is to solve the problem by makin…
On Estimating Maximum Matching Size in Graph Streams
Sepehr Assadi, Sanjeev Khanna, Yang Li
We study the problem of estimating the maximum matching size in graphs whose edges are revealed in a streaming manner. We consider both insertion-only streams and dynamic streams a…