Plays in YouTube's player, loaded from youtube-nocookie.com when you press Play. Watch on YouTube

Learn · Linear programming and its applications to computer science

Lecture 25 of 49Week 5

Lecture 25: Farkas Lemma

Prof. Rajat Mittal · IIT Kanpur

Credits and licence

From
Linear programming and its applications to computer science, IIT Kanpur (at NPTEL)
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
Tweens profiles and older. How courses are placed

All the lectures

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