On the complexity of linear programming
Nimrod Megiddo · Cambridge University Press eBooks · 1987
: This is a partial survey of results on the complexity of the linear programming problem since the ellipsoid method. The main topics are polynomial and strongly polynomial algorithms, probabilistic analysis of simplex algorithms, and recent interior point methods. Introduction Our purpose here is to survey theoretical developments in linear programming, starting from the ellipsoid method, mainly from the viewpoint of computational complexity. The survey does not attempt to be complete and naturally reflects the author's perspective, which may differ from the viewpoints of others. Linear programming is perhaps the most successful discipline of Operations Research. The standard form of the linear programming problem is to maximize a linear function c T x (c,xϵR n ) over all vectors x such that Ax = b and x ≥ 0. We denote such a problem by (A, b, c). Currently, the main tool for solving the linear programming problem in practice is the class of simplex algorithms proposed and developed by Dantzig [43]. However, applications of nonlinear programming methods, inspired by Karmarkar's work [79], may also become practical tools for certain classes of linear programming problems. Complexity-based questions about linear programming and related parameters of polyhedra (see, e.g., [66]) have been raised since the 1950s, before the field of computational complexity started to develop. The practical performance of the simplex algorithms has always seemed surprisingly good. In particular, the number of iterations seemed polynomial and even linear in the dimensions of problems being solved. Exponential examples were constructed only in the early 1970s, starting with the work of Klee and Minty [85].