Polynomial Inequalities Representing Polyhedra

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

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:	2003/08/13
Series (Serial Number):	ZIB-Report (03-25)
ZIB-Reportnumber:	03-25
Published in:	For a rev. vers. see ZR-04-53; the final version appeared in: Mathematical Programming 103 (2005) 35-44

Open Access