128 citations · 366 across the 34 of their papers we have counts for
40 papers
Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time
Ali Jadbabaie, Amin Saberi, Suvrit Sra
We prove two main algorithmic results in spectral discrepancy. First, we give a deterministic polynomial-time rounding theorem for rational positive semidefinite matrices of arbitr…
Sublinear Algorithms for TSP via Path Covers
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein +1
We study sublinear time algorithms for the traveling salesman problem (TSP). First, we focus on the closely related {\em maximum path cover} problem, which asks for a collection of…
Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing
Yiding Feng, Rad Niazadeh, Amin Saberi
Matching and pricing are two critical levers in two-sided marketplaces to connect demand and supply. The platform can produce more efficient matching and pricing decisions by batch…
Beating Greedy Matching in Sublinear Time
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein +1
We study sublinear time algorithms for estimating the size of maximum matching in graphs. Our main result is a -approximation algorithm which can be implemented…
Improved Online Contention Resolution for Matchings and Applications to the Gig Economy
Tristan Pollner, Mohammad Roghani, Amin Saberi +1
Motivated by applications in the gig economy, we study approximation algorithms for a \emph{sequential pricing problem}. The input is a bipartite graph between individu…
Algorithms Using Local Graph Features to Predict Epidemics
Yeganeh Alimohammadi, Christian Borgs, Amin Saberi
We study a simple model of epidemics where an infected node transmits the infection to its neighbors independently with probability . This is also known as the independent casca…