Ben Fish : Christofides the traveling salesperson: approximation algorithms

Posted by Roman Shvydkoy , part of the MATH Club.

At

Nov. 13, 2017, 4 p.m.

In

SEO 300

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.