MATH Club
Ben Fish
UIC
Christofides the traveling salesperson: approximation algorithms
Abstract: While most intro talks to the computational complexity of algorithms start by introducing NP-hardness, I'll take a more optimistic approach by talking about the power of provably-correct approximation algorithms, using metric TSP as an example to show the power of approximate solutions over exact solutions, and to explain what all these words mean.
Monday November 13, 2017 at 4:00 PM in SEO 300