Go backward to 26 Optimal Vertex
Go up to 5 Optimization
Go forward to 28 AOF Cube Programming
|
Go backward to 26 Optimal Vertex Go up to 5 Optimization Go forward to 28 AOF Cube Programming |
XHTML 1.0 |
| Input: | H-description of a polyhedron P ⊂ Qd, c ∈ Qd, C ∈ Q |
|---|---|
| Output: | "Yes" if there is a vertex v of P with cTv = C; "No" otherwise |
| Status (general): | Strongly NP-complete |
|---|---|
| Status (fixed dim.): | Polynomial time |
| Proved to be NP-complete by Chandrasekaran, Kabadi, and Murty [11] and strongly NP-complete by Fukuda, Liebling, and Margot [22]. The problem remains strongly NP-complete even if the input is restricted to polytopes [22]. |
| Related problems: | 25, 26 |
|---|
|
|
Why are some symbols not displayed correctly? |