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

Erik Demaine, Shay Mozes, Christian Sommer, Siamak Tazari

[Home] [Problem Sets] [Project] [Lectures] [Problem Session Notes] [Klein's Book]

Lecture 15 Video     [previous] [next]

[+] 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 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.

Download Video: 360p, 720p

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.