MA5325 Linear Programming: Theory and Algorithm Design
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
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
1. Linear Programming, K. G. Murthy, Springer, 1983.
2. The Design of Approximation Algorithms, D.P. Williamson, D. B. Shmoys, Cambridge University Press, 2010.