Matroid embedding


In combinatorics, a matroid embedding is a set system, where F is a collection of feasible sets, that satisfies the following properties:
  1. Every non-empty feasible set X contains an element x such that X\ is feasible;
  2. For every feasible subset X of a basis B, some element in B but not in X belongs to the extension ext of X, where ext is the set of all elements e not in X such that X∪ is feasible;
  3. For every superset A of a feasible set X disjoint from ext, A∪ is contained in some feasible set for either all or no e in ext;
  4. The collection of all subsets of feasible sets forms a matroid.
Matroid embedding was introduced by to characterize problems that can be optimized by a greedy algorithm.