Approximation Algorithms

3 Credits.

Graduate version of EN.601.435 . This course provides an introduction to approximation algorithms. Topics include vertex cover, TSP, Steiner trees, cuts, greedy approach, linear and semi-definite programming, primal-dual method, and randomization. Additional topics will be covered as time permits. There will be a final project. Recommended Background: EN.601.633 or equivalent. Students may receive credit for EN.601.435 or EN.601.635 , but not both.