The complexity of linear programming

Abstract

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. 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.