Zurück zu den Preprints des Jahres 2003


Polynomial inequalities representing polyhedra

by Bosse, Hartwig, Grötschel, Martin, Henk, Martin.

Series: 2003-27, Preprints

52B11 $n$-dimensional polytopes
14P10 Semialgebraic sets and related spaces
90C27 Combinatorial optimization

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.