23 citations · 101 across the 39 of their papers we have counts for
Showing 2014Show all
3 papers · 1 filter
cs.DS2014★ 17 cited
The Kadison-Singer Problem for Strongly Rayleigh Measures and Applications to Asymmetric TSP
Nima Anari, Shayan Oveis Gharan
Marcus, Spielman, and Srivastava in their seminal work \cite{MSS13} resolved the Kadison-Singer conjecture by proving that for any set of finitely supported independently distribut…
cs.DS2014★ 1 cited
Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP
Nima Anari, Shayan Oveis Gharan
We show that the integrality gap of the natural LP relaxation of the Asymmetric Traveling Salesman Problem is . In other words, there is a polynomial time alg…
cs.GT2014★ 7 cited
Mechanism Design for Crowdsourcing: An Optimal 1-1/e Competitive Budget-Feasible Mechanism for Large Markets
Nima Anari, Gagan Goel, Afshin Nikzad
In this paper we consider a mechanism design problem in the context of large-scale crowdsourcing markets such as Amazon's Mechanical Turk, ClickWorker, CrowdFlower. In these market…