Low-Dimensional Linear Programming
Presentation by: Marc Lebovitz
Comparison: Simplex vs. Seidel
The Simplex algorithm is exponential in the number of
constraints and the dimensions.
But, it performs better in practice and is the algorithm
of choice for
higher-dimensional LP problems.
With the Seidel algorithm, a
d-dimensional LP problem with n constraints can be solved in O(d! * n)
time. It's linear when you fix the dimension, and is the algorithm
of choice for lower-dimensional LP problems.
Robust implementations for both
can be found on-line:
Simplex
Seidel