Polynomial Inequalities Representing Polyhedra

Please always quote using this URN: urn:nbn:de:0297-zib-8284

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.

Metadaten
Author:	Hartwig Bosse, Martin Grötschel, Martin Henk
Document Type:	ZIB-Report
Tag:	polyhedra and polytopes; polyhedral combinatorics; polynomial inequalities; semi-algebraic sets; stability index
MSC-Classification:	14-XX ALGEBRAIC GEOMETRY / 14Pxx Real algebraic and real analytic geometry / 14P10 Semialgebraic sets and related spaces
	52-XX CONVEX AND DISCRETE GEOMETRY / 52Bxx Polytopes and polyhedra / 52B11 n-dimensional polytopes
	52-XX CONVEX AND DISCRETE GEOMETRY / 52Bxx Polytopes and polyhedra / 52B55 Computational aspects related to convexity (For computational geometry and algorithms, see 68Q25, 68U05; for numerical algorithms, see 65Yxx) [See also 68Uxx]
	90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
	90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Date of first Publication:	2004/12/22
Series (Serial Number):	ZIB-Report (04-53)
ZIB-Reportnumber:	04-53
Published in:	Appeared in: Mathematical Programming 103 (2005) 35-44

Open Access