The complexity of linear programming

A.H.G. RinnooyKan and J. Telgen

Statistica Neerlandica, 1981, vol. 35, issue 2, 91-107

Abstract: The simplex method for linear programming has always been very successful from a practical point of view. In the worst case, however, the method may require a computational effort that increases exponentially with problem size. Recently L.G. Khachianproposed an entirely different solution method whose running time is bounded by a polynomial function of problem size, thereby settling a major open problem in computational complexity theory. We review the developments preceding Khachian's discovery, describe the algorithm and discuss its implications.

Date: 1981
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1111/j.1467-9574.1981.tb00717.x

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:bla:stanee:v:35:y:1981:i:2:p:91-107

Ordering information: This journal article can be ordered from
http://www.blackwell ... bs.asp?ref=0039-0402

Access Statistics for this article

Statistica Neerlandica is currently edited by Miroslav Ristic, Marijtje van Duijn and Nan van Geloven

More articles in Statistica Neerlandica from Netherlands Society for Statistics and Operations Research
Bibliographic data for series maintained by Wiley Content Delivery ().