Zobrazeno 1 - 10
of 40
pro vyhledávání: '"Shayan Oveis Gharan"'
Publikováno v:
Integer Programming and Combinatorial Optimization ISBN: 9783031327254
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1d4ea0c4a572dc669032e1f31b9b6b35
https://doi.org/10.1007/978-3-031-32726-1_19
https://doi.org/10.1007/978-3-031-32726-1_19
Publikováno v:
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f519d8f907af4b2a1a545c443c4fadeb
https://doi.org/10.1145/3519935.3520062
https://doi.org/10.1145/3519935.3520062
Publikováno v:
Journal of Political Economy. 128:783-815
We introduce a simple model of dynamic matching in networked markets, where agents arrive and depart stochastically and the composition of the trade network depends endogenously on the matching alg...
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5782789955e466380744de1fc8a75f59
https://doi.org/10.1086/704761
https://doi.org/10.1086/704761
Publikováno v:
STOC
We prove tight mixing time bounds for natural random walks on bases of matroids, determinantal distributions, and more generally distributions associated with log-concave polynomials. For a matroid of rank $k$ on a ground set of $n$ elements, or more
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::cd9f18d3b10364b91dd573de693d5c08
https://doi.org/10.1145/3406325.3451091
https://doi.org/10.1145/3406325.3451091
We show that the natural Glauber dynamics mixes rapidly and generates a random proper edge-coloring of a graph with maximum degree $\Delta$ whenever the number of colors is at least $q\geq (\frac{10}{3} + \epsilon)\Delta$, where $\epsilon>0$ is arbit
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c9498214b8c0d081e9a1ff3df00b68cf
Publikováno v:
FOCS
We say a probability distribution $\mu$ is spectrally independent if an associated correlation matrix has a bounded largest eigenvalue for the distribution and all of its conditional distributions. We prove that if $\mu$ is spectrally independent, th
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1cfd5c107eaee1bc4777ab1d9e3c7047
https://doi.org/10.1109/focs46700.2020.00125
https://doi.org/10.1109/focs46700.2020.00125
Publikováno v:
STOC
We design a $1.49993$-approximation algorithm for the metric traveling salesperson problem (TSP) for instances in which an optimal solution to the subtour linear programming relaxation is half-integral. These instances received significant attention
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::404aa60defc6da477397e4ec9e3dba94
https://doi.org/10.1145/3357713.3384273
https://doi.org/10.1145/3357713.3384273
Publikováno v:
STOC
In “An Improved Approximation Algorithm for TSP,” Karlin, Klein, and Oveis Gharan design the first improvement over the classical 1.5 approximation algorithm of Christofides-Serdyukov after more than 40 years. Their algorithm first chooses a rand
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::90883f9b249b1fe46dd53c9b9bbd1d6d
Publikováno v:
Operations Research. 65:1043-1061
We present a randomized O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem (ATSP). This provides the first asymptotic improvement over the long-standing Θ(log n)-approximation bound stemming from the work of Fri
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6f204d0b5119b572a4efb7bf9512118d
https://doi.org/10.1287/opre.2017.1603
https://doi.org/10.1287/opre.2017.1603