Go up to 5 OptimizationGo forward to 26 Optimal Vertex |
XHTML 1.0 |

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

Why are some symbols not displayed correctly? |