Fast Algorithms for solving sparse LP problems

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?

• ArnoldNeumaier has a good point... Is there any structure in your matrix's sparsity pattern? – Paul Jul 25 '12 at 20:02