BAP: Lecture 13 (Apr 2, 2002)

The notes for this lecture are available in

In this lecture, we

Analyzed von Neumann's algorithm for linear programming. Material for this part of the lecture came from Condition Number Complexity of an Elementary Algorithm for Resolving a Conic Linear System by Marina Epelman and Rob Freund.
Related this analysis to a condition number, and stated the smoothed analysis of this condition number. Material for this part came from Smoothed Analysis of the Renegar's Condition Number for Linear Programming
by John Dunagan, Shang-Hua Teng, and Daniel A. Spielman