MA5325 Linear Programming: Theory and Algorithm Design

Course Details

Linear Programming: Basic feasible solutions and extreme points of a linear polytope, Change of basic feasible solutions and simplex algorithm, time complexity of simplex algorithm. Duality theory, Complementary slackness conditions, Farka's Lemma, LP Based ALgorithms: Min-Max relations and LP-duality, Maximum flow Minimum Cut Theorem Primal-dual algorithms for Minimum Ste cover, Minimum Vertex cover (half-integrality), Minimum Feedback Vertex Set, Algorithms for Maximum Satisfiability

Course References:

Text Books: 1. Combinatorial Optimization: Algorithms and Complexity, C. H. Papadimitrou, K. Steiglitz, Dover Publications, Inc, New York, 1998. 2. Approximation Algorithms, V. V, Vazirani, Springer 2003 Reference Books: 1. Linear Programming, K. G. Murthy, Springer, 1983. 2. The Design of Approximation Algorithms, D.P. Williamson, D. B. Shmoys, Cambridge University Press, 2010.