The course will deal with Optimization Algorithms, with special em- phasis on Combinatorial Methods.  The topics include classical methods of Linear Programming and Duality and their application to Combinatorial Optimization and Operations Research.  Polynomial algorithms for linear programming will be discussed, including the Ellipsoid Method and Interior point method (time permitting). In particular we will consider primal-dual methods in the context of classical graph theoretic problems like maximum flows, matching transshipment problem etc. Specific Topics are listed.

We will also consider related important NP-Hard optimization problems and integer programming.  The problems and methods find applications in Network Design and other domains of computer science as well as in areas of Management and Economic sciences.

References for the course:

(i) Course Book:  Combinatorial Optimization:  Algorithms and Com- plexity by C.H. Papadimitriou and K. Steiglitz (Dover Publications)

(ii) Combinatorial Optimization, Eugene Lawler (Dover)

(iii) Introduction to Algorithms,  Corman,  T.H.,  Leiserson,  C.E.,  and Rivest, R.L. (McGraw Hill)

There will be 4-5 homeworks, and (time permitting) a project.  Exams will be partly in class and part take-home.  HW 35%, Midterm 20%, final 30%, Project 10%.  There will be informal home works given in class.  Stu- dents are expected to attend/watch the lectures and solve the home works. These will carry a weight of 5%

Specific Topics

Topics:

Lecture 1: Introduction and Modeling

Lecture 2: Duality theorems: Illustration of Weak Duality

Lecture 3: Illustration of weak Duality in LP

Lecture 4: Convex function and Sets

Lecture 5: Condition for convexity, Local-global optimality

Lecture 6: Convex Optimization, Lagrangian Dual function,

Lecture 7: KKT conditions, LP Duality, LP and Polytopes