Your browser is unsupported

We recommend using the latest version of IE11, Edge, Chrome, Firefox or Safari.

Nov 18 2019

Anna Karlin

CS Distinguished Lecture Series

November 18, 2019

11:00 AM - 12:00 PM


1043 ERF


Chicago, IL 60607

Presenter: Anna Karlin, Microsoft Professor of Computer Science & Engineering at the University of Washington

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 exists which returns a solution at most 3/2 times worse than the optimal. Since then, however, no better approximation algorithm has been found. Finding a polynomial time algorithm which breaks this 3/2 barrier is a famous open problem in theoretical computer science. In this talk, an overview of research towards this goal will be provided, and a new sub-3/2 approximation algorithm for an interesting special case will be presented, so-called "half integral" TSP instances. This presentation is of joint work with Nathan Klein and Shayan Oveis Gharan.

Speaker Bio: Anna R. Karlin is the Microsoft Professor of Computer Science and Engineering at the Paul G. Allen School of Computer Science at the University of Washington. She received her PhD from Stanford University in 1987. Before arriving at the University of Washington, she spent 5 years as a researcher at (what was then) Digital Equipment Corporation's Systems Research Center. Her research is primarily in theoretical computer science: the design and analysis of algorithms, particularly algorithmic game theory, probabilistic and online algorithms. Karlin is coauthor of the book “Game Theory, Alive,” published in 2017 by the American Mathematical Society. She is a Fellow of the Association for Computing Machinery and a member of the American Academy of Arts and Sciences.

Faculty Host: Xiaorui Sun,

Contact: Professor Xiaorui Sun,


Xiaorui Sun

Date posted

Oct 31, 2019

Date updated

Nov 18, 2019