backup forward

Go backward to 7 Number of Vertices
Go up to 2 Coordinate Descriptions
Go forward to 9 Recognizing Integer Polyhedra
XHTML 1.0

8 Feasible Basis Extension

Input: Polytope P given as {xRs : A x = b, x0}, 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?


backup forward Why are some symbols not displayed correctly?