Karmarkar’s Linear Programming Algorithm

J. N. Hooker
Additional contact information
J. N. Hooker: Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, Pennsylvania 15213

Interfaces, 1986, vol. 16, issue 4, 75-90

Abstract: N. Karmarkar’s new projective scaling algorithm for linear programming has caused quite a stir in the press, mainly because of reports that it is 50 times faster than the simplex method on large problems. It also has a polynomial bound on worst-case running time that is better than the ellipsoid algorithm’s. Radically different from the simplex method, it moves through the interior of the polytope, transforming the space at each step to place the current point at the polytope’s center. The algorithm is described in enough detail to enable one to write one’s own computer code and to understand why it has polynomial running time. Some recent attempts to make the algorithm live up to its promise are also reviewed.

Keywords: programming; linear: algorithms (search for similar items in EconPapers)
Date: 1986
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/inte.16.4.75 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orinte:v:16:y:1986:i:4:p:75-90

Access Statistics for this article

More articles in Interfaces from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().