TY - GEN A1 - Rambau, Jörg T1 - Triangulierungen von Punktmengen und Polyedern N2 - Dieser Report wurde im Sommersemester 2000 an der TU Berlin in einer Spezialvorlesung ü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ührende Themen reguläre Triangulierungen, Sekundärpolytope, bistellare Operationen, höhere Stasheff-Tamari-Halbordnungen und Triangulierungen mit wenigen bzw. gar keinen Flips behandelt. Ein Kapitel über Enumeration und Optimierung beschließt die Zusammenstellung. T3 - ZIB-Report - 00-46 KW - point configuration KW - triangulation KW - polytope KW - polyhedron KW - Gale diagram KW - secondary polytope KW - cyclic polytope KW - graph of all triangulations KW - conn Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6145 ER - TY - GEN A1 - Grötschel, Martin T1 - Cardinality Homogeneous Set Systems, Cycles in Matroids, and Associated Polytopes N2 - 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})$. T3 - ZIB-Report - 02-19 KW - Cycles in Matroids KW - cardinality homogeneous set systems KW - polytopes KW - greedy algorithm KW - polyhedral combinatorics Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6868 ER - TY - GEN A1 - Stephan, Rüdiger T1 - Cardinality Constrained Combinatorial Optimization: Complexity and Polyhedra N2 - 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ö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. T3 - ZIB-Report - 08-48 KW - Combinatorial Optimization KW - Cardinality Constraints KW - Matroids KW - Cardinality Forcing Inequalities Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11026 SN - 1438-0064 ER - TY - GEN A1 - Stephan, Rüdiger T1 - On the cardinality constrained matroid polytope N2 - 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ö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. T3 - ZIB-Report - 08-08 KW - Matroid-Polytop KW - Kardinalitätsbeschränkung KW - Separationsalgorithmus KW - Matroid Polytope KW - Cardinality constraints KW - Separation algorithm Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10614 SN - 1438-0064 ER -