Clutter
A clutter is a set family with no member containing another member. In other context, they are also called Sperner families.
Let C be a clutter on ground set V. We investigate the following linear system LP(C) associated with C:
min
- A clutter {\mathcal C} packs if both LP({\mathcal C}) and its dual have integral optimal solutions for w={\mathbf 1}.
- A clutter {\mathcal C} has the packing property if both LP({\mathcal C}) and its dual have integral optimal solutions if w \in \{0,1, +\infty\}^V.
- A clutter {\mathcal C} has the max flow min cut property (MFMC property for short) if both LP({\mathcal C}) and its dual have integral optimal solutions if w \in \mathbb{Z}_+^V. Equivalently, if LP({\mathcal C}) is TDI.
- A clutter {\mathcal C} is ideal if LP({\mathcal C}) has an integral optimal solution if w \in \mathbb{Z}_+^V. Equivalently, if LP({\mathcal C}) describes an integer polyhedron.
The blocker of a clutter is the clutter of inclusionwise minimal transversals. Given a clutter {\mathcal C} and an element v \in V, the deletion of v means the restriction of the clutter to V-v, while the contraction of v is the clutter on ground set V-v formed by the inclusionwise minimal elements of \{X-v: X \in {\mathcal C}\}. A minor of {\mathcal C} is a clutter obtained by a sequence of deletions and contractions.
A comprehensive description on the topic can be found in Cornuéjols' book [1]. See also the Wikipedia article.
References
- ↑ G. Cornuéjols, Combinatorial Optimization: Packing and Covering, author link