Input: | H-description of a polyhedron P Ì Q,
^{d}c Î Q^{d} |
---|---|

Output: | inf { and, if the infimum is finite, a
point where the infimum is attained.c^{T}x : x Î P } Î QÈ {-¥ , ¥ } |

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 No strongly polynomial time algorithm (performing a number of
arithmetic operations that is bounded polynomially in |

Related problems: | 26, 27, 28 |
---|