BAP: Lecture 12 (Mar 21, 2002)

The notes for this lecture are available in

latex,
postscript, and
pdf

Note that these notes contain improvements made by the scribe on the material presented in class!

In this lecture, we first proved the strong duality theorem for general linear programs. We then introduced Renegar's condition numbers and used them to bound how much the value of a linear program can change as it is perturbed. Material for this part of the lecture came from:

@article{renegar95,
  author = "James Renegar",
  title = "Incorporating condition measures into the complexity theory
    of linear programming",
  journal = "SIAM Journal on Optimization",
  volume = "5",
  pages = "506--524",
  year = "1995",
  url = "citeseer.nj.nec.com/renegar95incorporating.html"
}