MA 5012   Approximation Algorithms

Course contents:

Complexity of optimization Problems:
The complexity classes P and NP; Karp reduction; decision, solution and evaluation vertions of an optimization problem.

Design Techniques for Approximation Algorithms:
Greedy Methods for Knapsac, independent set and TSP; Sequential algorithms for scheduling, bin packing and graph coloring; Local search algorithms for Maximum Cut and TSP;

Approximation Classes:
Approximate solutions with guaranteed absolute error and relative error; Approximability and non-approximability of TSP; Limits to approximability (gap technique); The complexity classes PTAS and FPTAS; Strong NP-completeness and pseudo-polynomiality;

Approximation algorithms for various problems:
Set-cover, graph coloring, minimum multi-cut, edge coloring, bin packing.

Text Books:

1.      G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. M. Protasi, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, 1999.


1.      V. Vazirani, Approximation Algorithms, Springer 2005. (indian edition available)

2.      C. H. Papadimitriou and K. Steiglitz, Combinatorial optimization: Algorithms and Complexity, PHI 2001.

3.      J. Kleinberg and E. Tardos, Algorithm Design, Pearson India, 2007.