@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{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{Stephan, author = {Stephan, R{\"u}diger}, title = {Cardinality Constrained Combinatorial Optimization: Complexity and Polyhedra}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11026}, number = {08-48}, abstract = {Given a combinatorial optimization problem and a subset \$N\$ of natural numbers, we obtain a cardinality constrained version of this problem by permitting only those feasible solutions whose cardinalities are elements of \$N\$. In this paper we briefly touch on questions that addresses common grounds and differences of the complexity of a combinatorial optimization problem and its cardinality constrained version. Afterwards we focus on polytopes associated with cardinality constrained combinatorial optimization problems. Given an integer programming formulation for a combinatorial optimization problem, by essentially adding Gr{\"o}tschel's cardinality forcing inequalities, we obtain an integer programming formulation for its cardinality restricted version. Since the cardinality forcing inequalities in their original form are mostly not facet defining for the associated polyhedra, we discuss possibilities to strengthen them.}, language = {en} } @misc{Stephan, author = {Stephan, R{\"u}diger}, title = {On the cardinality constrained matroid polytope}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10614}, number = {08-08}, abstract = {Edmonds showed that the so-called rank inequalities and the nonnegativity constraints provide a complete linear description of the matroid polytope. By essentially adding Gr{\"o}tschel's cardinality forcing inequalities, we obtain a complete linear description of the cardinality constrained matroid polytope which is the convex hull of the incidence vectors of those independent sets that have a feasible cardinality. Moreover, we show how the separation problem for the cardinality forcing inequalities can be reduced to that for the rank inequalities. We also give necessary and sufficient conditions for a cardinality forcing inequality to be facet defining.}, language = {en} }