The Complexity of the Simplex Algorithm
Metadata
Show full item recordDate
1984-08Citation
Currie, James D. The Complexity of the Simplex Algorithm; A thesis submitted to the Faculty of Graduate Studies and Research in partial fulfillment of the requirements for the degree of Master of Science, Department of Mathematics and Statistics, Carleton University, August 1984.
Abstract
The thesis begins by giving background in linear programming and Simplex methods. Topics covered include the duality theorem, Lemke's algorithm, and the pathological programs of Klee-Minty.
Because of the bad behaviour of Klee-Minty programs, the behaviour of the Simplex algorithm is only good on average. To take such an average, certain assumptions on the distribution of linear programs are introduced and discussed.
A geometrical meaning is given for the number of steps Lemke's algorithm takes to solve a program. This gives rise to a formula bounding the average number of steps taken. This formula is heuristically justified in an original way.
The formula is combinatorially simplified, to get a bound on the complexity of Simplex.