Input: | H-description of a polyhedron P Ì Q^{d}, c Î Q^{d} |
---|---|
Output: | inf { c^{T}v : 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). |
Related problems: | 1, 25, 27 |
---|