MA6210 Combinatorial Optimization
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:
Texts 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.
References:
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.