Matroid embedding: Difference between revisions
Jump to navigation
Jump to search
imported>Bkell m formatting touchups |
imported>Spamakin m Grammatical Fix (embedding -> embeddings) |
||
| Line 6: | Line 6: | ||
# The collection of all subsets of feasible sets forms a [[matroid]]. | # The collection of all subsets of feasible sets forms a [[matroid]]. | ||
Matroid | Matroid embeddings were introduced by {{harvtxt|Helman|Moret|Shapiro|1993}} to characterize problems that can be optimized by a [[greedy algorithm]]. | ||
== References == | == References == | ||
Latest revision as of 16:18, 24 November 2025
Template:Short description In 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 non-empty 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, where ext(X) is 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 e or no e in ext(X).
- The collection of all subsets of feasible sets forms a matroid.
Matroid embeddings were introduced by Script error: No such module "Footnotes". to characterize problems that can be optimized by a greedy algorithm.
References
- Script error: No such module "citation/CS1".