[Coin-lpsolver] LP - complexity

[svoboda at fi.muni.cz]

Hello,

I've been using CLP. I hope I'm right if I suppose that CLP is based on 
simplex method designed by G. Dantzig. In general, the worst-case time 
complexity for simplex method is exponetial. Fortunately, if using spare 
matrices, we can get (average) polynomial complexity. May I ask anybody to 
get a proof for this hypothesis?

Moreover, I found a ref. to polynomial algorithm:

  Karmarkar, N. "A New Polynomial-Time Algorithm for Linear Programming."
 	Combinatorica 4, 373-395, 1984.

Is there any relationship between Karmarkar's alg. (based on Interior 
point methods) and CLP?


With regards

  David Svoboda