03-27
Polynomial inequalities representing polyhedra
by Bosse, Hartwig; Grötschel, Martin; Henk, Martin
Preprint series: 03-27, Preprints
- MSC:
- 52B11 $n$-dimensional polytopes
- 14P10 Semialgebraic sets and related spaces
- 90C27 Combinatorial optimization
Abstract: Our main result is that every n-dimensional polytope can be described by at most (2n-1) polynomial inequalities and, moreover, these polynomials can explicitly be constructed. For an n-dimensional pointed polyhedral cone we prove the bound 2n-2 and for arbitrary polyhedra we get a constructible representation by 2n polynomial inequalities.
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.