686
eng
reportzib
0
2002-11-15
2002-11-15
--
Cardinality Homogeneous Set Systems, Cycles in Matroids, and Associated Polytopes
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})$.
02-19
687
urn:nbn:de:0297-zib-6868
10.1137/1.9780898718805.ch8
Appeared in: The sharpest cut. The impact of Manfred Padberg and his work Papers from the workshop in honor of Manfred Padberg's 60th birthday, Berlin, Germany, Oct. 11-13, 2001. Philadelphia, PA: SIAM 2004. Pp. 99-120
Martin GrÃ¶tschel
ZIB-Report
02-19
eng
uncontrolled
Cycles in Matroids
eng
uncontrolled
cardinality homogeneous set systems
eng
uncontrolled
polytopes
eng
uncontrolled
greedy algorithm
eng
uncontrolled
polyhedral combinatorics
Informatik, Informationswissenschaft, allgemeine Werke
Matroids, geometric lattices [See also 52B40, 90C27]
Matroids (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) [See also 05B35, 52Cxx]
Computational aspects related to convexity (For computational geometry and algorithms, see 68Q25, 68U05; for numerical algorithms, see 65Yxx) [See also 68Uxx]
Combinatorial optimization
Polyhedral combinatorics, branch-and-bound, branch-and-cut
ZIB Allgemein
GrÃ¶tschel, Martin
https://opus4.kobv.de/opus4-zib/files/686/ZR-02-19.ps
https://opus4.kobv.de/opus4-zib/files/686/ZR-02-19.pdf