Cardinality Homogeneous Set Systems, Cycles in Matroids, and Associated Polytopes
Cardinality Homogeneous Set Systems, Cycles in Matroids, and Associated Polytopes
复制标题
基数齐次集合系统、拟阵中的循环以及相关的多面体
DOI：
10.1137/1.9780898718805.ch8
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
M. Grötschel
中科院分区：
文献类型：
--
作者：
M. Grötschel
有限集$E$的幂集${\cal C}$的子集${\cal C}$称为基数齐次，如果当${\cal C}$包含某个集合$F$时，${\cal C}$包含基数$|F|$的所有集合$E$。这样的集合系统${\cal}$的例子是一致拟阵的电路集和循环集以及$E$的所有偶数或所有奇基数子集的集合。对于每一个基数齐次集合系统${\cal C}$，我们关联了多面体$P({\cal C})$、${\cal C}$中所有集合的关联向量的凸包，并给出了$P({\cal C})$的一个完备的、非冗余的线性描述。我们证明了贪心算法对P({\cal C})$上的任何线性函数都是最优的，给出了对偶线性规划的显式最优解，并给出了一类P({\cal C})$的多项式时间分离算法。
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})$.