Optimization Online


How bad is a gradient algorithm for linear programming?

Peter A. Bruijs(p.a.bruijs***at***wxs.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 - interior-point 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
Entry Accepted: 04/20/2011
Entry Last Modified: 04/20/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society