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