Go backward to 25 Linear Programming Go up to 5 Optimization Go forward to 27 Vertex With Specified Objective Value |
XHTML 1.0 |
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 |
---|
Why are some symbols not displayed correctly? |