|
|
|
|
|
Matroid EmbeddingIn combinatorics, a matroid embedding is a set system (F, E), where F is a collection of feasible sets, that satisfies the following properties: - (Accessibility Property) every nonempty feasible set X contains an element x such that X\{x} is feasible;
- (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;
- (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);
- the collection of all subsets of every feasible set 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 - Helman, Paul; Moret, Bernard M. E.; Shapiro, Henry D. (1993). An exact characterization of greedy structures. SIAM J. Discrete Math. 6 (2), 274–283.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|