backup forward

Go backward to 26 Optimal Vertex
Go up to 5 Optimization
Go forward to 28 AOF Cube Programming
XHTML 1.0

27 Vertex With Specified Objective Value

Input: H-description of a polyhedron P ⊂ Qd, cQd, 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].

backup forward Why are some symbols not displayed correctly?