The complexity of linear programming

A.H.G. Rinnooy Kan*, J. Telgen

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

12 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)91-107
Number of pages17
JournalStatistica Neerlandica
Issue number2
Publication statusPublished - 1 Jan 1981
Externally publishedYes


Dive into the research topics of 'The complexity of linear programming'. Together they form a unique fingerprint.

Cite this