In their 1972 paper ‘How good is the simplex algorithm ?’ Klee and Minty present a class of problems the simplex algorithm for linear programming (LP) is not able to solve in a polynomial way. Later developments have resulted in algorithms by Khachiyan and Karmarkar that do solve LP in a polynomial way, although the bounds they generate are not exclusively based on LP’s problem dimensions m and n. Until now it is an open question whether there exists a strongly polynomial algorithm solving LP in O(m,n) operations. In this paper we try to identify characteristics of present algorithms that might hinder in attaining such a result, and look at the possibilities a strongly gradient oriented algorithm might offer in this respect.
Citation
unpublished report no actual affiliation, produced after retirement april 2011
Article
View How bad is a gradient algorithm for linear programming?