Lecture 18: Linear Programming Fall 2011

From IFORS Education Resources
Jump to: navigation, search

By: Avrim Blum


Overview

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


Personal tools