| Course Code: CS508 Course Name: Optimization Methods Prerequisites: 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 |