CODEWITHSUNDEEP
simplex
Anupama Karunarathna
Anupama Karunarathna

Reputation: 117

Simplex Algorithm - Worst Case

Its given that worst case time complexity of simplex algorithm is O(2^n). What is the worst case in simplex algorithm? To calculate time complexity I want to know about the worst case.

Upvotes: 1

Views: 1223

Answers (1)

G Oliveira
G Oliveira

Reputation: 323

In the worst case scenario, simplex needs to visit 2^n vertice points (Klee & Minty 1972), which could also be the same point being visited repeatedly if you consider degeneration.

Nonetheless, the simplex algorithm has polynomial average-case complexity under various probability distributions. By such principle, it was proven that slightly random pertubations (which bearely change the original data) to the input of simplex would cause the expected running time to become polynomial (Spielman and Teng - 2001).

References:

Upvotes: 1

Related Questions