| Input: | H-description of a polyhedron P Ì Qd, c Î Qd |
|---|---|
| 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]). |
| Related problems: | 26, 27, 28 |
|---|