LP Solvers

LP solvers are general algorithms in solving Linear Programming problems

LP Solvers	Description	Running Times (i.e. Memory Complexity))
Graphical Method	visually or manually check optimum	N/A
Simplex Method	key idea is to explore the vertices of the polytope, moving along the edges, until an optimal vertex is reached many variants of the Simplex Method	exponential time bounded (average case is much faster) in terms of how large the values occur in the variables and constraints
Interior-Point Method	starts from a point in the polytope and proceeds towards the optimum in a step-by-step descent fashion many variants of the Interior-Point Method	weakly polynomial bounded in terms of how large the values occur in the variables and constraints

both the Simplex Method and Interior-Point Method are not strongly polynomial time bounded.

weakly bounded - where the worst-case running time is bounded in terms of the value of variables and constraints only
strongly bounded - where the worst-case running time is bounded in number of variables and constraints only (i.e. independently from values of variables and constraints)

no LP Solver is found to be strongly polynomial time bounded