Follow
Shayan Oveis Gharan
Shayan Oveis Gharan
Associate Professor, University of Washington
Verified email at cs.washington.edu - Homepage
Title
Cited by
Cited by
Year
Multiway spectral partitioning and higher-order cheeger inequalities
JR Lee, SO Gharan, L Trevisan
Journal of the ACM (JACM) 61 (6), 1-30, 2014
4202014
Thickness and information in dynamic matching markets
M Akbarpour, S Li, SO Gharan
Journal of Political Economy 128 (3), 783-815, 2020
3022020
Online stochastic matching: Online actions based on offline statistics
VH Manshadi, SO Gharan, A Saberi
Mathematics of Operations Research 37 (4), 559-573, 2012
2912012
An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
A Asadpour, MX Goemans, A Mądry, SO Gharan, A Saberi
Operations Research 65 (4), 1043-1061, 2017
2642017
A randomized rounding approach to the traveling salesman problem
SO Gharan, A Saberi, M Singh
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, 550-559, 2011
2042011
Submodular maximization by simulated annealing
S Oveis Gharan, J Vondrák
194*2010
Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid
N Anari, K Liu, SO Gharan, C Vinzant
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 1-12, 2019
1932019
A (slightly) improved approximation algorithm for metric TSP
AR Karlin, N Klein, SO Gharan
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing …, 2021
1672021
Spectral independence in high-dimensional expanders and applications to the hardcore model
N Anari, K Liu, SO Gharan
SIAM Journal on Computing, FOCS20-1-FOCS20-37, 2021
1512021
Monte Carlo Markov chain algorithms for sampling strongly Rayleigh distributions and determinantal point processes
N Anari, SO Gharan, A Rezaei
Conference on Learning Theory, 103-115, 2016
1342016
Minimizing movement
ED Demaine, MT Hajiaghayi, H Mahini, AS Sayedi-Roshkhar, ...
ACM Transactions on Algorithms (TALG) 5 (3), 1-30, 2009
1232009
Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids
N Anari, SO Gharan, C Vinzant
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 35-46, 2018
1202018
Simultaneous approximations for adversarial and stochastic online budgeted allocation
VS Mirrokni, SO Gharan, M Zadimoghaddam
Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete …, 2012
1062012
Nash social welfare for indivisible items under separable, piecewise-linear concave utilities
N Anari, T Mai, SO Gharan, VV Vazirani
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete …, 2018
882018
Effective-resistance-reducing flows, spectrally thin trees, and asymmetric TSP
N Anari, SO Gharan
2015 IEEE 56th Annual Symposium on Foundations of Computer Science, 20-39, 2015
842015
Approximating the expansion profile and almost optimal local graph clustering
SO Gharan, L Trevisan
2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, 187-196, 2012
812012
Nash social welfare, matrix permanent, and stable polynomials
N Anari, SO Gharan, A Saberi, M Singh
arXiv preprint arXiv:1609.07056, 2016
802016
Log-concave polynomials III: Mason's ultra-log-concavity conjecture for independent sets of matroids
N Anari, K Liu, SO Gharan, C Vinzant
arXiv preprint arXiv:1811.01600, 2018
732018
Partitioning into expanders
SO Gharan, L Trevisan
Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete …, 2014
622014
Improved Cheeger's inequality: Analysis of spectral partitioning algorithms through higher order spectral gap
TC Kwok, LC Lau, YT Lee, S Oveis Gharan, L Trevisan
Proceedings of the forty-fifth annual ACM symposium on Theory of computing …, 2013
622013
The system can't perform the operation now. Try again later.
Articles 1–20