BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//UIC
BEGIN:VEVENT
UID:2026051202475320191118T11000020191118T1200006a0294d94e8a9@uic.edu
CATEGORIES:MEETING
STATUS:TENTATIVE
DTSTAMP:20191031T024450
DTSTART:20191118T110000
DTEND:20191118T120000
SUMMARY:Anna Karlin
DESCRIPTION: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 | Event post: https://cs.uic.edu/events?page_id=3329
LOCATION:1043 ERF   Chicago IL 60607
CLASS:PRIVATE
END:VEVENT
END:VCALENDAR