MA6210       COMBINATORIAL OPTIMIZATION

Review of Mathematical Programming, Integer programming, Branch and Bound techniques, Travelling salesman problem.

 

Computational complexity, Ellipsoidal and Karmarkar algorithms, Primal Dual algorithms.

 

Network Problems: Shortest path algorithms, minimum spanning trees, matching algorithms, Chinese postman problem, Flow in networks and algorithms.

Books:

1. C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice Hall of India, 1998.