  


How bad is a gradient algorithm for linear programming?
Peter A. Bruijs(p.a.bruijswxs.nl) Abstract: 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. Keywords: linear programming  simplex algorithm  ellipsoid method  interiorpoint methods  gradient methods  computational complexity Category 1: Linear, Cone and Semidefinite Programming Category 2: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: unpublished report no actual affiliation, produced after retirement april 2011 Download: [PDF] Entry Submitted: 04/20/2011 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  