ABSTRACT
The traveling saleswoman 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, we will give an overview of research towards this goal and describe a new sub-3/2 approximation algorithm for an interesting special case, so-called "half integral" TSP instances.
This is joint work with Nathan Klein and Shayan Oveis Gharan.
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 Ph.D. from Stanford University in 1987. Before coming to 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. She 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.
