Linear Programming is a Shrinking Watermelon and Optimality is a Black Hole

John O. McClain
Additional contact information
John O. McClain: Graduate School of Business and Public Administration, Cornell University, Malott Hall, Ithaca, New York 14853

Interfaces, 1980, vol. 10, issue 3, 106-107

Abstract: It has been said “If the world were linear, Dantzig would be King.” That tribute recognizes G. B. Dantzig as the inventor of the simplex method for solving a class of mathematical problems called Linear Programming (LP). Now there is a new contender for the throne. L. G. Khachiyan, a Russian mathematician, has developed a new method [Gács, P., L. Lovász. 1979. Khachiyan's algorithm for linear programming. Technical Report STAN-CS-79-750, Department of Computer Science, Stanford University, Stanford, California, p. 12; Khachiyan, L. 1979. A polynomial algorithm in linear programming. Doklady Akademiia Nauk SSSR Novaia Seriia 224 (5) 1093--1096 (English translation in Soviet Mathematics Doklady 20 (1) 191--194.)] that will almost certainly beat simplex for some LP problems. Even though such learned journals as The New York Times have covered this new concept, it has not yet been adequately captured in everyday prose. This note is offered as a remedy.

Keywords: programming; linear: theory (search for similar items in EconPapers)
Date: 1980
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/inte.10.3.106 (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:10:y:1980:i:3:p:106-107

Access Statistics for this article

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