MA5325 Linear Programming: Theory and Algorithm Design (New Course)
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.