MA6210 Combinatorial Optimization (modified)

Course Details

Complexity of optimization problems: 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 max-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); 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.

Course References:

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.

Reference Books:
1. V. Vazirani, Approximation Algorithms, Springer 2005.
2. C. H. Papadimitriou, K. Steiglitz, Combinatorial optimization: Algorithms and Complexity, PHI 2001.
3. J. Kleinberg, E. Tardos, Algorithm Design, Pearson India, 2007.