CS508OPTIMIZATION METHODS3-0-0-6

Pre-requisites : NIL

Syllabus :
Introduction to Linear Programming: Connections with Geometry. Simplex Method: Duality Theorem. Complementary Slackness. Farkes' Lemma. Revised Simplex Method.General LP Problems: Infeasibility. Sensitivity Analysis. Primal-Dual Algorithm: Applications to Network Flow and Matching. Efficient Algorithm: Linear Programming in fixed dimensions. Randomized Linear Programming. Integer Linear Programming: Total Unimodularity. Semidefinite Programming: Application to MAXSAT problems.

Texts :
1. V. Chavtal, Linear Programming, W. H. Freeman and Company, New York, 1983.
2. C. H. Papadimitriou and K. steiglitz, Combinatorial optimization: Algorithms and Complexity, Dover Publications, Inc., New York, 1998.

References :
1. M. Grotschel, L. Lovasz and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, John Wiley & Sons, Inc., New York, 1998.
2. W. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver, Combinatorial Optimization, John Wiley & Sons, Inc., New York, 1998.
3. R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
4. Related publications in Journals/Conferences