@misc{Rambau, author = {Rambau, J{\"o}rg}, title = {Triangulierungen von Punktmengen und Polyedern}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6145}, number = {00-46}, abstract = {Dieser Report wurde im Sommersemester 2000 an der TU Berlin in einer Spezialvorlesung {\"u}ber Triangulierungen von Punktmengen und Polyedern als Skriptum verwendet. Nach einem motivierenden Kapitel werden grundlegende Begriffe und Konstruktionen in der Theorie der Triangulierungen von Punktmengen und Polyedern vorgestellt. Danach werden als weiterf{\"u}hrende Themen regul{\"a}re Triangulierungen, Sekund{\"a}rpolytope, bistellare Operationen, h{\"o}here Stasheff-Tamari-Halbordnungen und Triangulierungen mit wenigen bzw. gar keinen Flips behandelt. Ein Kapitel {\"u}ber Enumeration und Optimierung beschließt die Zusammenstellung.}, language = {de} } @misc{GroetschelHenk, author = {Gr{\"o}tschel, Martin and Henk, Martin}, title = {On the Representation of Polyhedra by Polynomial Inequalities}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6826}, number = {02-15}, abstract = {A beautiful result of Br{\"o}cker and Scheiderer on the stability index of basic closed semi-algebraic sets implies, as a very special case, that every \$d\$-dimensional polyhedron admits a representation as the set of solutions of at most \$d(d+1)/2\$ polynomial inequalities. Even in this polyhedral case, however, no constructive proof is known, even if the quadratic upper bound is replaced by any bound depending only on the dimension. Here we give, for simple polytopes, an explicit construction of polynomials describing such a polytope. The number of used polynomials is exponential in the dimension, but in the 2- and 3-dimensional case we get the expected number \$d(d+1)/2\$.}, language = {en} } @misc{Groetschel, author = {Gr{\"o}tschel, Martin}, title = {Cardinality Homogeneous Set Systems, Cycles in Matroids, and Associated Polytopes}, doi = {10.1137/1.9780898718805.ch8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6868}, number = {02-19}, abstract = {A subset \${\cal C}\$ of the power set of a finite set \$E\$ is called cardinality homogeneous if, whenever \${\cal C}\$ contains some set \$F\$, \${\cal C}\$ contains all subsets of \$E\$ of cardinality \$|F|\$. Examples of such set systems \${\cal C}\$ are the sets of circuits and the sets of cycles of uniform matroids and the sets of all even or of all odd cardinality subsets of \$E\$. With each cardinality homogeneous set system \${\cal C}\$, we associate the polytope \$P({\cal C})\$, the convex hull of the incidence vectors of all sets in \${\cal C}\$, and provide a complete and nonredundant linear description of \$P({\cal C})\$. We show that a greedy algorithm optimizes any linear function over \$P({\cal C})\$, give an explicit optimum solution of the dual linear program, and provide a polynomial time separation algorithm for the class of polytopes of type \$P({\cal C})\$.}, language = {en} } @misc{BosseGroetschelHenk, author = {Bosse, Hartwig and Gr{\"o}tschel, Martin and Henk, Martin}, title = {Polynomial Inequalities Representing Polyhedra}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8284}, number = {04-53}, 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.}, language = {en} } @misc{BosseGroetschelHenk, author = {Bosse, Hartwig and Gr{\"o}tschel, Martin and Henk, Martin}, title = {Polynomial Inequalities Representing Polyhedra}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7473}, number = {03-25}, 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.}, language = {en} }