17 citations · 97 across the 38 of their papers we have counts for
Showing 2014 · cs.DSShow all
2 papers · 2 filters
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…