About this event
Talk abstract:
The traveling salesperson problem (TSP) is one of the most celebrated and well-studied NP-complete problems we know. A classic result from Christofides in the 70s tells us that a fast algorithm returns a solution at most 3/2 times worse than the optimal. Since then, however, no better approximation algorithm has been found until very recently, when Nathan Klein, Shayan Oveis Gharan, and I presented a new sub-3/2 approximation algorithm for the problem.
In this talk, I will survey the history of this fascinating problem and describe some of the critical ideas that went into our new result.
Brief bio:
Anna R. Karlin is a Professor at the Paul G. Allen School of Computer Science and Engineering and the Bill & Melinda Gates Chair of Computer Science and Engineering at the University of Washington. Her research is primarily in the design and analysis of algorithms and in algorithmic game theory. Karlin is coauthor of the book “Game Theory, Alive” published by the American Mathematical Society, a co-winner of the 2021 ACM Paris Kanellakis Theory and Practice Award, an ACM Fellow, a member of the American Academy of Arts and Sciences, the National Academy of Sciences and the National Academy of Engineering.
Zoom information
Click here to register: https://nsf.zoomgov.com/webinar/register/WN_jdCKRE_eQ9KFiX5Pvof34w
Or an H.323/SIP room system:
H.323: 161.199.138.10 (US West) or 161.199.136.10 (US East)
Meeting ID: 160 142 4050
Passcode: 726342
SIP: 1601424050@sip.zoomgov.com
Passcode: 726342
After registering, you will receive a confirmation email containing information about joining the webinar.