[+] PTAS for planar TSP: Klein's framework for approximation schemes in planar graphs 
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 polynomialtime algorithms with approximation ratio strictly below 3/2. TSP is NPhard even for planar graphs. In this lecture, we discuss a lineartime 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. 
Lecture notes, page 1/7 •
[previous page] •
[next page] •
[PDF]
Lecture notes, page 1/7 • [previous page] • [next page] • [PDF] 

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email Erik.