MA5325 Linear Programming: Theory and Algorithm Design (New Course)


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.