Editing Matroid (section)

==Algorithms==
Several important combinatorial optimization problems can be solved efficiently on every matroid. In particular:

* Finding a '''maximum-weight independent set in a [[weighted matroid]]''' can be solved by a [[greedy algorithm]]. This fact may even be used to characterize matroids: if a family ''F'' of sets, closed under taking subsets, has the property that, no matter how the sets are weighted, the greedy algorithm finds a maximum-weight set in the family, then ''F'' must be the family of independent sets of a matroid.<ref name="Ox64">{{harvp|Oxley|1992|p=64}}</ref>

* The '''[[matroid partitioning]] problem''' is to partition the elements of a matroid into as few independent sets as possible, and the '''matroid packing problem''' is to find as many disjoint spanning sets as possible. Both can be solved in polynomial time, and can be generalized to the problem of computing the rank or finding an independent set in a matroid sum.

* A '''[[matroid intersection]]''' of two or more matroids on the same ground set is the family of sets that are simultaneously independent in each of the matroids. The problem of finding the largest set, or the maximum weighted set, in the intersection of two matroids can be found in [[polynomial time]], and provides a solution to many other important combinatorial optimization problems. For instance, [[maximum matching]] in [[bipartite graph]]s can be expressed as a problem of intersecting two [[partition matroid]]s. However, finding the largest set in an intersection of three or more matroids is [[NP-complete]].