Course10610435649 lectures
Linear programming and its applications to computer science
Prof. Rajat Mittal · IIT Kanpur
About
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 and learn about linear programming, but also see its uses in different areas of computer science (algorithms, algorithmic game theory, theoretical computer science, machine learning).
Intended audience: Senior undergraduate (3rd or 4th year) and masters/phd students in CSE
Prerequisites: Linear algebraBasic Linear Algebra - https://nptel.ac.in/courses/111101115Linear Algebra - https://nptel.ac.in/courses/111104137https://nptel.ac.in/courses/111106135
Lectures
Week 1
- Lecture 1 : Linear programming, an example
- Lecture 2 : Introduction to linear programming
- Lecture 3 : Gaussian elimination with examples
- Lecture 4 : Summary of Gaussian elimination
Week 2
- Lecture 5: Vector space over real numbers
- Lecture 6: Linear operators
- Lecture 7: Solutions of linear equations
- Lecture 8: Resource allocation as LP
- Lecture 9: Approximate degree as LP
- Lecture 10: Equivalent LP's
Week 3
- Lecture 11: Introduction to convexity
- Lecture 12: Different kind of convex sets
- Lecture 13: Feasible region of LP
- Lecture 14: Proof of Weyl's theorem
- Lecture 15: Definition of convex functions
- Lecture 16: Properties of convex functions and examples
Week 4
- Lecture 17: Basic feasible solution
- Lecture 18: BFS and vertices
- Lecture 19: Simplex algorithm
- Lecture 20: Details of simplex algorithm
- Lecture 21: Starting BFS
- Lecture 22: Degeneracy
- Lecture 23: Introduction to duality
Week 5
- Lecture 24: Hyperplane separation theorems
- Lecture 25: Farkas Lemma
- Lecture 26: How to take dual
- Lecture 27: Examples of taking dual
- Lecture 28: Strong Duality
- Lecture 29: Proof of strong duality
- Lecture 30: Complementary slackness
Week 6
- Lecture 31: Introduction to algorithmic game theory
- Lecture 32: Nash equilibrium
- Lecture 33: Minimax and Nash equilibrium
- Lecture 34: Deterministic communication complexity
- Lecture 35: Randomized communication complexity
- Lecture 36: Yao's minimax theorem
- Lecture 37: Lower bounds using Yao's minimax
Week 7
- Lecture 38: Set disjointness problem
- Lecture 39: LP for max flow problem
- Lecture 40: LP for min cut problem
- Lecture 41: max flow = min cut
- Lecture 42: Primal dual approach
- Lecture 43: Primal dual for max flow
Week 8
Syllabus and materials
At NPTEL, as the course publishes them.
Credits and licence
- Institution
- IIT Kanpur
- Department
- Computer Science and Engineering
- Teacher
- Prof. Rajat Mittal
- Level
- Undergraduate
- Language
- English
- Subjects
- Computer science, Engineering
- Source
- NPTEL
- Licence
- CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
- Attribution
- NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
- Who can watch
- NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed