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
UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/686
UR - https://nbn-resolving.org/urn:nbn:de:0297-zib-6868
ER -