Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Cardinality Homogeneous Set Systems, Cycles in Matroids, and Associated Polytopes

Please always quote using this URN: urn:nbn:de:0297-zib-6868
  • 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})$.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Martin Grötschel
Document Type:ZIB-Report
Tag:Cycles in Matroids; cardinality homogeneous set systems; greedy algorithm; polyhedral combinatorics; polytopes
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Bxx Designs and configurations (For applications of design theory, see 94C30) / 05B35 Matroids, geometric lattices [See also 52B40, 90C27]
52-XX CONVEX AND DISCRETE GEOMETRY / 52Bxx Polytopes and polyhedra / 52B40 Matroids (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) [See also 05B35, 52Cxx]
52-XX CONVEX AND DISCRETE GEOMETRY / 52Bxx Polytopes and polyhedra / 52B55 Computational aspects related to convexity (For computational geometry and algorithms, see 68Q25, 68U05; for numerical algorithms, see 65Yxx) [See also 68Uxx]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Date of first Publication:2002/11/15
Series (Serial Number):ZIB-Report (02-19)
ZIB-Reportnumber:02-19
Published in: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
DOI:https://doi.org/10.1137/1.9780898718805.ch8
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.