Prerona Chatterjee

Linear Programming and Combinatorial Optimisation

• Introductory course for incoming graduate students and senior undergraduate students.
• Class Timings:
• Location:
• Lecture Notes:

 

References

• Understanding and Using Linear Programming (Jiří Matoušek , Bernd Gärtner)
• Combinatorial Optimization: Algorithms and Complexity (Christos H. Papadimitriou, Kenneth Steiglitz)
• Lecture notes on "Topics in Linear Programming" (Rajat Mittal)

 

Grading

• Assignments (take-home) - 20%
• Mid-sem (in-class) - 30%
• Seminar (in groups, in-class) - 10%
• End-sem (in-class) - 40%

 

Problem Sets

 

Lecture Summary

Week 1: Formulating problems as an LP and basics of LP

• Lecture 1:
• Lecture 2:
• Lecture 3:

Week 2: No classes since I will be away for an ICTS workshop.

Week 3: The Simplex Algorithm and basics of Duality

• Lecture 4:
• Lecture 5:
• Lecture 6:

Weeks 4 and 5: Duality Theory

• Lecture 7:
• Lecture 8:
• Lecture 9:
• Lecture 10:

Week 6 and 7: Minimax Theorems and the Primal Dual Method

• Lecture 11:
• Lecture 12:
• Lecture 13:
• Lecture 14:

Weeks 8 and 9: Student Talks: More Applications of Duality

• Talk 1:
• Talk 2:
• Talk 3:
• Talk 4:
• Talk 5:
• Talk 6:
• Talk 7:

Week 10: No class since I will be visiting IIT Bombay.

Week 11: Ellipsoid and Interior Point Methods

• Lecture 15:
• Lecture 16:

Weeks 12, 13 and 14: Semi-definite Programming

• Lecture 17:
• Lecture 18:
• Lecture 19:
• Lecture 20:
• Lecture 21:
• Lecture 22: