Go backward to 7 Number of Vertices
Go up to 2 Coordinate Descriptions
Go forward to 9 Recognizing Integer Polyhedra
|
Go backward to 7 Number of Vertices Go up to 2 Coordinate Descriptions Go forward to 9 Recognizing Integer Polyhedra |
XHTML 1.0 |
| Input: | Polytope P given as {x ∈ Rs : A x = b, x ≥ 0}, a set S ⊆ {1, …, s} |
|---|---|
| Output: | "Yes" if there is a feasible basis with an index set containing S, "No" otherwise |
| Status (general): | NP-complete |
|---|---|
| Status (fixed dim.): | Polynomial time |
|
See Murty [49] (Garey and Johnson [23], Problem
[MP4]). For fixed dimension, one can enumerate all bases in
polynomial time.
The problem can be reformulated as follows. Let P be defined by a finite set H of affine halfspaces and let S be a subset of H. Does ∩ {h ∈ H : h ∉ S} contain a vertex which is also a vertex of P? |
|
|
Why are some symbols not displayed correctly? |