Fast Algorithms for solving sparse LP problems

Question

For solving a very sparse LP: {min $cx$: s.t.: $A_{m \times n}x=b$ , $x\geq 0$}, which one of the following algorithms is faster?

1. Logarithmic barrier method
2. Other variants of the interior point method
3. Simplex method

What is the best worst case complexity? In general, which algorithm performs well in practice for sparse matrices?

Answer 1

The speed of all three methods (which are in fact generic patterns for algorithms rather than algorithms) depends a lot on who implemented which details. A sensible implementation of each method can be far better than a poor implementation of any of the others.

The complexity in the sparse case depends a lot on the sparsity pattern, and there are no results on the general sparse case.