<h3>MA5325 Linear Programming: Theory and Algorithm Design</h3>
<br/>
<h4>Course Details</h4>
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
<br/>
<h4>Course References:</h4>
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.