Premium
The complexity of linear programming
Author(s) -
RinnooyKan A.H.G.,
Telgen J.
Publication year - 1981
Publication title -
statistica neerlandica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.52
H-Index - 39
eISSN - 1467-9574
pISSN - 0039-0402
DOI - 10.1111/j.1467-9574.1981.tb00717.x
Subject(s) - simplex algorithm , computational complexity theory , linear programming , mathematics , bounded function , time complexity , mathematical optimization , function (biology) , algorithm , polynomial , computer science , point (geometry) , revised simplex method , mathematical analysis , geometry , evolutionary biology , biology
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. K hachian proposed 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 K hachian 's discovery, describe the algorithm and discuss its implications.