| 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 |
|---|