IIT Kanpur · Computer Science

Linear programming and its applications to computer science

Prof. Rajat Mittal · 2025 · 49 free video lectures

Linear programming is a special class of mathematical optimization problems where the constraints as well as the cost function is linear. This class of problems have known efficient algorithms, deep structural properties and wide applications in various fields. In this course we not only introduce…

▶ Play on Open Lecture HallCourse page ↗

Lectures

  1. Lecture 1 : Linear programming, an example
  2. Lecture 2 : Introduction to linear programming
  3. Lecture 3 : Gaussian elimination with examples
  4. Lecture 4 : Summary of Gaussian elimination
  5. Lecture 5: Vector space over real numbers
  6. Lecture 6: Linear operators
  7. Lecture 7: Solutions of linear equations
  8. Lecture 8: Resource allocation as LP
  9. Lecture 9: Approximate degree as LP
  10. Lecture 10: Equivalent LP's
  11. Lecture 11: Introduction to convexity
  12. Lecture 12: Different kind of convex sets
  13. Lecture 13: Feasible region of LP
  14. Lecture 14: Proof of Weyl's theorem
  15. Lecture 15: Definition of convex functions
  16. Lecture 16: Properties of convex functions and examples
  17. Lecture 17: Basic feasible solution
  18. Lecture 18: BFS and vertices
  19. Lecture 19: Simplex algorithm
  20. Lecture 20: Details of simplex algorithm
  21. Lecture 21: Starting BFS
  22. Lecture 22: Degeneracy
  23. Lecture 23: Introduction to duality
  24. Lecture 24: Hyperplane separation theorems
  25. Lecture 25: Farkas Lemma
  26. Lecture 26: How to take dual
  27. Lecture 27: Examples of taking dual
  28. Lecture 28: Strong Duality
  29. Lecture 29: Proof of strong duality
  30. Lecture 30: Complementary slackness
  31. Lecture 31: Introduction to algorithmic game theory
  32. Lecture 32: Nash equilibrium
  33. Lecture 33: Minimax and Nash equilibrium
  34. Lecture 34: Deterministic communication complexity
  35. Lecture 35: Randomized communication complexity
  36. Lecture 36: Yao's minimax theorem
  37. Lecture 37: Lower bounds using Yao's minimax
  38. Lecture 38: Set disjointness problem
  39. Lecture 39: LP for max flow problem
  40. Lecture 40: LP for min cut problem
  41. Lecture 41: max flow = min cut
  42. Lecture 42: Primal dual approach
  43. Lecture 43: Primal dual for max flow
  44. Lecture 44: Set cover problem
  45. Lecture 45: Rounding for set cover
  46. Lecture 46: Analysis of rounding
  47. Lecture 47: Algorithm for set cover
  48. Lecture 48: Linear regression through LP
  49. Lecture 49: Linear classifiers through LP

From NPTEL (IITs and IISc) · CC BY-NC-SA. More from IIT Kanpur.

Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights