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
2702014
Online stochastic matching: Online actions based on offline statistics
VH Manshadi, SO Gharan, A Saberi
Mathematics of Operations Research 37 (4), 559-573, 2012
2052012
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
2022017
Thickness and information in dynamic matching markets
M Akbarpour, S Li, SO Gharan
Journal of Political Economy 128 (3), 783-815, 2020
184*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
1682011
Submodular maximization by simulated annealing
S Oveis Gharan, J VondrŠk
141*2010
Minimizing movement
ED Demaine, MT Hajiaghayi, H Mahini, AS Sayedi-Roshkhar, ...
ACM Transactions on Algorithms (TALG) 5 (3), 1-30, 2009
1072009
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
932016
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
762012
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
622015
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
572012
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
472019
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
472018
Nash social welfare, matrix permanent, and stable polynomials
N Anari, SO Gharan, A Saberi, M Singh
arXiv preprint arXiv:1609.07056, 2016
442016
Partitioning into expanders
SO Gharan, L Trevisan
Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete†…, 2014
442014
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
442011
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
432013
On variants of the matroid secretary problem
S Oveis Gharan, J VondrŠk
Algorithms–ESA 2011, 335-346, 2011
40*2011
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
392018
A generalization of permanent inequalities and applications in counting and optimization
N Anari, SO Gharan
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing†…, 2017
292017
The system can't perform the operation now. Try again later.
Articles 1–20