Abstract collage of overlapping, bright-colored glowing circles
Event ended Lectures

A slightly improved approximation algorithm for the Traveling Salesperson Problem by Anna R. Karlin

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.