Lecture 18: Linear Programming Fall 2011
By: Avrim Blum
In this lecture we describe a very general problem called linear programming that can be used to express a wide variety of different kinds of problems. We can use algorithms for linear program- ming to solve the max-flow problem, solve the min-cost max-flow problem, find minimax-optimal strategies in games, and many other things. We will primarily discuss the setting and how to code up various problems as linear programs At the end, we will briefly describe some of the algorithms for solving linear programming problems.
Link to material: http://www.cs.cmu.edu/~avrim/451f11/lectures/lect1101.pdf