• English
    • français
  • English 
    • English
    • français
View Item 
  •   WinnSpace Home
  • Department of Mathematics and Statistics
  • James D. Currie
  • View Item
  •   WinnSpace Home
  • Department of Mathematics and Statistics
  • James D. Currie
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

The Complexity of the Simplex Algorithm

Thumbnail

View Open

currie-thecomplexityofthesimplexalgorithm.pdf (1.855Mb)

Metadata

Show full item record

Author

Currie, James

Uri

http://hdl.handle.net/10680/1695

Date

1984-08

Citation

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.

Collections

  • James D. Currie

Report a copyright concern

Contact Us | Send Feedback
 

 

Browse

All of WinnSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

My Account

LoginRegister

Report a copyright concern

Contact Us | Send Feedback