It has been an open question whether the Linear Programming (LP) problem can be solved in strong polynomial time. The simplex algorithm does not offer a polynomial bound, and polynomial algorithms by Khachiyan and Karmarkar don’t have the strong characteristic. The curious fact that non-linear algorithms would be needed to deliver the strongest complexity result for LP served as the motivation to look at feasible gradient methods. Experiments and theory show that a linear algorithm has the desired strong characteristic.
Citation
unpublished, no affiliation
Article
View A strong polynomial gradient algorithm in Linear Programming