Anna Karlin
CS Distinguished Lecture Series
November 18, 2019
11:00 AM - 12:00 PM
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, xiaorui@uic.edu
Contact: Professor Xiaorui Sun, xiaorui@uic.edu
Date posted
Oct 31, 2019
Date updated
Nov 18, 2019