combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...

, 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'' \ 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'' ∪ is feasible. # Closure–congruence property: For every superset ''A'' of a feasible set ''X'' disjoint from ext(''X''), ''A'' ∪ 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 In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...

. Matroid embedding was introduced by to characterize problems that can be optimized by a

greedy algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locall ...

References

*{{citation , last1 = Helman , first1 = Paul , last2 = Moret , first2 = Bernard M. E. , author2-link = Bernard Moret , last3 = Shapiro , first3 = Henry D. , doi = 10.1137/0406021 , issue = 2 , journal =

SIAM Journal on Discrete Mathematics '' SIAM Journal on Discrete Mathematics'' is a peer-reviewed mathematics journal published quarterly by the Society for Industrial and Applied Mathematics (SIAM). The journal includes articles on pure and applied discrete mathematics. It was esta ...

, mr = 1215233 , pages = 274–283 , title = An exact characterization of greedy structures , volume = 6 , year = 1993, citeseerx = 10.1.1.37.1825

Embedding In mathematics, an embedding (or imbedding) is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup. When some object X is said to be embedded in another object Y, the embedding is giv ...