Go backward to 25 Linear Programming
Go up to 5 Optimization
Go forward to 27 Vertex With Specified Objective Value

26 Optimal Vertex

Input: H-description of a polyhedron P Ì Qd, c Î Qd
Output: inf { cTv : v vertex of P } Î QÈ {¥ } and, if the infimum is finite, a vertex where the infimum is attained.
Status (general): Strongly NP-hard
Status (fixed dim.): Polynomial time
Proved to be strongly NP-hard by Fukuda, Liebling, and Margot [22]. By linear programming this problem can be solved in polynomial time if P is a polytope. In fixed dimension one can compute all vertices of P in polynomial time (see Problem 1).