Effective-Resistance-Reducing Flows, Spectrally Thin Trees and Asymmetric TSP
Event details
| Date | 10.02.2015 |
| Hour | 16:00 › 17:00 |
| Speaker | Shayan Oveis Gharan (University of Washington) |
| Location |
INF 211
|
| Category | Conferences - Seminars |
We show that the integrality gap of the natural LP relaxation
of the Asymmetric Traveling Salesman Problem (ATSP) is at most polyloglog(n). In other words, there is a polynomial time algorithm that approximates the value of the optimum tour within a factor of polyloglog(n).
This is the first significant improvement over the classical O~(log n) approximation factor for ATSP. Our proof builds on recent developments in operator theory, in particular recent resolution of the Kadison Singer conjecture by Marcus, Spielman and Srivastava.
In this talk, I will highlight the main ideas of our proof.
This is a joint work with Nima Anari.
Short bio:
Shayan Oveis Gharan is an assistant professor at CSE department at UW. He received his PhD from the MS&E department at Stanford University. Before joining UW he spent one and a half years as a postdoctoral Miller fellow at UC Berkeley where his host was Umesh Vazirani. He has done his undergraduate studies at the Computer Engineering department at Sharif University.
His main research includes Algorithm design, Graph Theory and Applied Probability. He has received several awards for his works on Traveling Salesman Problem.
of the Asymmetric Traveling Salesman Problem (ATSP) is at most polyloglog(n). In other words, there is a polynomial time algorithm that approximates the value of the optimum tour within a factor of polyloglog(n).
This is the first significant improvement over the classical O~(log n) approximation factor for ATSP. Our proof builds on recent developments in operator theory, in particular recent resolution of the Kadison Singer conjecture by Marcus, Spielman and Srivastava.
In this talk, I will highlight the main ideas of our proof.
This is a joint work with Nima Anari.
Short bio:
Shayan Oveis Gharan is an assistant professor at CSE department at UW. He received his PhD from the MS&E department at Stanford University. Before joining UW he spent one and a half years as a postdoctoral Miller fellow at UC Berkeley where his host was Umesh Vazirani. He has done his undergraduate studies at the Computer Engineering department at Sharif University.
His main research includes Algorithm design, Graph Theory and Applied Probability. He has received several awards for his works on Traveling Salesman Problem.
Practical information
- Informed public
- Free
Organizer
- Ola Svensson