Go backward to 25 Linear Programming
Go up to 5 Optimization
Go forward to 27 Vertex With Specified Objective Value
|
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 ⊂ 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). |
| Related problems: | 1, 25, 27 |
|---|
|
|
Why are some symbols not displayed correctly? |