BAP: Lecture 12 (Mar 21, 2002)
The notes for this lecture are available in
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:
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"