up forward

Go up to 5 Optimization
Go forward to 26 Optimal Vertex
XHTML 1.0

25 Linear Programming

Input: H-description of a polyhedron P ⊂ Qd, cQd
Output: inf { cTx : x ∈ P } ∈ Q ∪ {-∞, ∞ } and, if the infimum is finite, a point where the infimum is attained.
Status (general): Polynomial time; no strongly polynomial time algorithm known
Status (fixed dim.): Linear time in m (the number of inequalities)
The first polynomial time algorithm was a variant of the ellipsoid algorithm due to Khachiyan [38]. Later, also interior point methods solving the problem in polynomial time were discovered (Karmarkar [37]).

Megiddo found an algorithm solving the problem for a fixed number d of variables in O(m) arithmetic operations (Megiddo [44]).

No strongly polynomial time algorithm (performing a number of arithmetic operations that is bounded polynomially in d and the number of half-spaces rather than in the coding lengths of the input coordinates) is known. In particular, no polynomial time variant of the simplex algorithm is known. However, a randomized version of the simplex algorithm solves the problem in (expected) subexponential time (Kalai [36], Matousek, Sharir, and Welzl [42]).


up forward Why are some symbols not displayed correctly?