Course Details
Subject {L-T-P / C} : CS6211 : Combinatorial Optimization { 3-0-0 / 3}
Subject Nature : Theory
Coordinator : Prof. Pankaj Kumar Sa
Syllabus
Combinatorial Problems Combinatorial Structures Combinatorial Objects: Generation, Enumeration Subsets k-Element subsets Permutations Complexity Graphs Linear Programming and Algorithms Integer Programming: Integer hull of a polyhedron Unimodular Transformation Dual Integrality Spanning Trees and Arborescence Shortest Paths Network Flows Minimum Cost Flows Maximum Matching Weighted Matching Matroids: Duality Matroids Intersection, Partitioning Polymatroids Submodular Functions Approximation Algorithms Backtracking Branch and Bound Dynamic Programming Local Search: Deterministic and Stochastic Algorithms Optimal versus final solution single and multicriteria constrained optimization Convergence analysis Markov Chains Design strategies Hill Climbing Simulated Annealing Aspects of SA Convergence Tabu Search Aspects of TS Convergence Genetic Algorithms Aspects of GA Convergence Parallelization of search.
Course Objectives
- -
Course Outcomes
-
Essential Reading
- Bernhard Korte and Jens Vygen, Combinatorial Optimization: Theory and Algorithms, Springer-Verlag Heidelberg
- Christos H. Papadimitriou and Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications
Supplementary Reading
- Alexander Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer-Verlag Heidelberg
- Donald L. Kreher and Douglas R. Stinson, Combinatorial Algorithms: Generation, Enumeration, and Search, CRC Press