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
2952014
Online stochastic matching: Online actions based on offline statistics
VH Manshadi, SO Gharan, A Saberi
Mathematics of Operations Research 37 (4), 559-573, 2012
2232012
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
2152017
Thickness and information in dynamic matching markets
M Akbarpour, S Li, SO Gharan
Journal of Political Economy 128 (3), 783-815, 2020
207*2020
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
1742011
Submodular maximization by simulated annealing
S Oveis Gharan, J VondrŠk
148*2010
Minimizing movement
ED Demaine, MT Hajiaghayi, H Mahini, AS Sayedi-Roshkhar, ...
ACM Transactions on Algorithms (TALG) 5 (3), 1-30, 2009
1112009
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
1012016
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
842012
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
662015
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
652019
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
632012
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
572018
Nash social welfare, matrix permanent, and stable polynomials
N Anari, SO Gharan, A Saberi, M Singh
arXiv preprint arXiv:1609.07056, 2016
532016
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
502018
The asymmetric traveling salesman problem on graphs with bounded genus
SO Gharan, A Saberi
Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete†…, 2011
492011
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
472013
Partitioning into expanders
SO Gharan, L Trevisan
Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete†…, 2014
462014
On variants of the matroid secretary problem
S Oveis Gharan, J VondrŠk
Algorithms–ESA 2011, 335-346, 2011
42*2011
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
362021
The system can't perform the operation now. Try again later.
Articles 1–20