828
eng
reportzib
0
2004-12-22
2004-12-22
--
Polynomial Inequalities Representing Polyhedra
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.
04-53
829
urn:nbn:de:0297-zib-8284
Appeared in: Mathematical Programming 103 (2005) 35-44
Hartwig Bosse
Martin GrÃ¶tschel
Martin Henk
ZIB-Report
04-53
eng
uncontrolled
polyhedra and polytopes
eng
uncontrolled
semi-algebraic sets
eng
uncontrolled
polyhedral combinatorics
eng
uncontrolled
polynomial inequalities
eng
uncontrolled
stability index
Informatik, Informationswissenschaft, allgemeine Werke
Semialgebraic sets and related spaces
n-dimensional polytopes
Computational aspects related to convexity (For computational geometry and algorithms, see 68Q25, 68U05; for numerical algorithms, see 65Yxx) [See also 68Uxx]
Combinatorial optimization
Polyhedral combinatorics, branch-and-bound, branch-and-cut
ZIB Allgemein
GrÃ¶tschel, Martin
https://opus4.kobv.de/opus4-zib/files/828/ZR-04-53.ps
https://opus4.kobv.de/opus4-zib/files/828/ZR-04-53.pdf