6.889: Algorithms for Planar Graphs and Beyond (Fall 2011)

In the Traveling Salesman Problem (TSP) we need to find a shortest tour visiting all the nodes of a graph. For general graphs, there have been recent algorithmic breakthroughs: researchers have found polynomial-time algorithms with approximation ratio strictly below 3/2.

TSP is NP-hard even for planar graphs. In this lecture, we discuss a linear-time approximation scheme for planar graphs. For any constant ε>0, there is an algorithm that finds a tour of length at most (1+ε) times the optimal length of a tour. (Unless P=NP, such an approximation scheme cannot exist for general graphs.)

The TSP algorithm also serves as a beautiful example of a more general framework for efficient approximation schemes in planar graphs.

It may be helpful to review (/ first watch) some of the materials of Lecture 8 on approximation schemes in planar graphs.