Matroid embedding

In combinatorics, a matroid embedding is a set system (F, E), where F is a collection of feasible sets, that satisfies the following properties:

  1. (Accessibility Property) Every non-empty feasible set X contains an element x such that X\{x} is feasible;
  2. (Extensibility Property) For every feasible subset X of a basis (i.e., maximal feasible set) B, some element in B but not in X belongs to the extension ext(X) of X, or the set of all elements e not in X such that X∪{e} is feasible;
  3. (Closure-Congruence Property) For every superset A of a feasible set X disjoint from ext(X), A∪{e} is contained in some feasible set for either all or no e in ext(X);
  4. The collection of all subsets of feasible sets forms a matroid.

Matroid embedding was introduced by Helman et al. in 1993 to characterize problems that can be optimized by a greedy algorithm.

References

This article is issued from Wikipedia - version of the 11/29/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.