Motivation
Greedy algorithms do not succeed merely because their choices look locally attractive. They need a structural reason why an early choice can be incorporated into an optimum. A matroid captures one such structure: independent sets are closed under taking subsets, and a smaller independent set can be augmented using an element of a larger one. These properties support an exchange proof for a broad weighted greedy algorithm.
The result below finds a maximum-weight base, meaning a maximal independent set. If weights can be negative, that is a different objective from finding a maximum-weight independent set of arbitrary size. The distinction is part of the theorem, not an implementation detail.
Definitions
Definition 2.8.1
(Matroid, independent set and base)
A finite matroid is a pair , where is finite and is nonempty and satisfies:
- Hereditary property: if and , then .
- Augmentation property: if and , some satisfies .
A base is an inclusion-maximal independent set. Repeated augmentation shows that every independent set extends to a base, and any two bases have the same cardinality: otherwise the smaller could be augmented from the larger. Give each element a real weight .
Definition 2.8.2
(Greedy scan in nonincreasing weight order)
The greedy algorithm orders the elements by nonincreasing weight, breaking ties in any fixed order. It scans the order and inserts an element exactly when the chosen set remains independent. It scans the entire ground set, even when some weights are negative.
Theorems
Lemma 2.8.3
(Extension using a base)
If is a base, is independent, and is independent with , then some makes a base.
Theorem 2.8.4
(Weighted matroid greedy theorem)
For every finite matroid and real weight function, the greedy algorithm returns a maximum-weight base.
Proof sketch or proof idea
Proof
(Extending an independent set to a base by augmentation)
To prove the extension lemma, start with . As long as its size is smaller than , augmentation supplies an element of that can be added while retaining independence. At size the resulting set contains , all of , and all but one element of . It is a base and has the displayed form.
Proof
(An optimum base contains the greedy choices)
For the greedy theorem, the final chosen set is maximal: an element rejected when scanned cannot become addable after more elements are selected, because a subset of an independent set would have to be independent. Thus the result is a base. Maintain an optimum base containing the greedy choices made so far. Initially any optimum base works. Suppose greedy next adds to previously chosen set . If , retain . Otherwise, the lemma gives for which is a base.
The element cannot have been scanned before : at its scan time, the chosen set was a subset of , and adding would have remained independent because . Greedy would then have selected it, contradicting . Therefore comes after in the fixed nonincreasing order and . The exchanged base is no lighter than the optimum and is therefore also optimum; it contains the new greedy set. Induction proves that an optimum base contains the final greedy base, so they are equal.
Proof X-ray
The rejected-element argument
The exchange produces a removable element from the single fact that is independent; this is where augmentation is used, through the lemma. The scan order then supplies the weight comparison. Heredity does two jobs: it makes a rejection permanent, and it shows that would have been accepted had it been scanned before , since the chosen set was then contained in . The argument closes by induction on the number of greedy choices, always keeping an optimum base that contains every choice so far, so the final greedy base equals an optimum base. Ties do not matter, because only is used. Without augmentation the lemma fails, and the hereditary-family example in a later section shows greedy returning a non-optimal set.
Worked examples
Worked example 2.8.5
(A cardinality constraint)
Let independent sets be all subsets of of size at most two, with weights . Greedy takes and rejects because the capacity is full. The resulting base has maximum weight seven.
Worked example 2.8.6
(A graphic matroid)
For an undirected graph, let independent edge sets be forests. Greedy in decreasing edge weight adds an edge when it does not create a cycle. On a connected graph its output is a maximum-weight spanning tree, the maximum-weight counterpart of Kruskal's minimum-tree algorithm.
Worked example 2.8.7
(Tied weights)
If all elements of a rank-two matroid have equal weight, different fixed tie orders can lead to different bases. Every base has two elements and therefore the same total weight. The theorem permits any fixed tie order.
Common mistakes
Common mistake
(Maximum base versus maximum independent set)
In a one-element rank-one matroid with weight , the only base is the singleton of weight , while the empty independent set has weight zero. Scanning all elements solves the maximum-base problem, not this unrestricted independent-set problem.
Common mistake
(Hereditary closure alone is not enough)
Hereditary closure alone is not enough for the theorem. The augmentation property is used to extend a greedy choice into a base and to make all bases the same size. A proof for an arbitrary family of feasible sets cannot silently assume it.
Why the exchange lemma follows from augmentation
Let be a base of size containing the current independent set , and suppose is independent with . The augmentation axiom applies to the current set and the independent set whenever the current set has fewer than elements. It supplies an element of not already present that can be added. Repeat until the new independent set has size .
The final set contains , the new element , and exactly elements of . Since has elements, exactly one of them was omitted. Calling that element gives . It is independent and has the common base size , so it is a base. This proof uses the augmentation property repeatedly; the name "exchange" is a conclusion, not an extra axiom assumed without explanation.
The greedy proof maintains an optimum base containing the choices made so far, not necessarily the original optimum base throughout. When an exchange is needed, the witnessing optimum may change. The new base is no lighter, and since it cannot exceed the original optimum's weight, its weight equals the optimum. This is how an algorithm can make a sequence of local choices while retaining a global optimality certificate at every step.
A hereditary family where greedy fails
Counterexample mode
Heredity without augmentation
Claim: for every hereditary family and every real weight function, descending greedy returns a maximum-weight base. Let and let the independent sets be all subsets of together with all subsets of . This family is hereditary, but augmentation fails for and : neither nor can be added to . With weights and , descending greedy chooses and cannot add either other element, obtaining weight three. The independent set has weight four. The family is not a matroid, so the theorem does not apply. The repair is the augmentation property: it is exactly what excludes this family, and with it greedy is optimal.
The example also has maximal independent sets of different sizes, one and two. In a matroid that cannot happen: if a maximal independent set were smaller than another independent set, augmentation would contradict its maximality. Equal base size is a consequence of the axioms, not an additional hidden assumption.
Why forests form a matroid
For a finite undirected graph, take to be its edge set and call a set independent when it contains no cycle. Removing edges from a forest cannot create a cycle, so heredity holds. For augmentation, let forests satisfy . If no edge of joined distinct connected components of the forest , every edge of would lie within one of those components. In a component with vertices, an acyclic graph has at most edges. Summing over the components would give , a contradiction. Thus some edge of joins distinct components and can be added without making a cycle.
In a connected graph, every maximal forest is a spanning tree. The maximum-base theorem applied to the graphic matroid therefore proves the decreasing-weight version of Kruskal's algorithm. Reversing the order, or equivalently negating weights, gives the minimum spanning tree version. The theorem covers ties because no step of the proof requires strict weight inequalities.
Bases versus arbitrary independent sets
When all weights are nonnegative, a maximum-weight independent set can be extended to a base without reducing its weight. Thus a maximum-weight base is also optimal among all independent sets. With negative weights, extension can make the weight worse, as the one-element example shows. The scan-all algorithm deliberately returns a base and may include negative elements when necessary to reach one.
To maximize weight among independent sets with arbitrary real weights, discard all negative-weight elements from consideration and run the same greedy rule on the restriction to positive-weight elements. Every independent set can discard its negative elements without reducing its weight; zero-weight elements can also be omitted without changing its weight. The positive restriction is a matroid, and an optimum positive independent set can be extended to a base of that restriction while increasing or preserving weight. The greedy theorem therefore proves the resulting positive-element set is optimal for the unrestricted independent-set objective. This is a related corollary, not the objective of the scan-all base algorithm.
Concept lensStructural
The greedy base is a base of every weight threshold
For a real , let . Greedy scans all of before any other element, so its output meets in a maximal independent subset of , of size . Conversely, a base has maximum weight exactly when for every : its weight is plus a sum of the sizes against nonnegative gaps between consecutive weights, and no base can exceed the rank in any layer.
Complexity and what the oracle means
Sorting elements takes comparisons. The generic algorithm then makes one independence query per element. Its actual running time depends on how independence is tested and how the chosen set is represented. Treating an independence query as a constant-time oracle gives an oracle-call count, not automatically a concrete implementation bound.
For the graphic matroid, a disjoint-set structure can test whether an edge joins different current components; its precise cost depends on the chosen union and find operations. For the cardinality matroid, independence is checked by the current set size. The same abstract proof applies to both, while their implementations and complexity analyses differ.
To check a proposed output, verify independence and maximality and compare its weight with a separately justified upper bound. Independence alone does not prove maximum weight. The greedy exchange proof supplies the optimality guarantee for the algorithm's own output; an arbitrary independent set of the correct size need not be maximum weight.
Tracing a graphic exchange
Worked example 2.8.8
(Tracing the exchange on a four-vertex graph)
Consider four vertices with edges of weights respectively. Descending greedy first accepts and . It rejects because those three edges form a cycle, accepts , and then rejects . Its spanning tree has weight .
To see how the exchange proof certifies this answer, start instead with the spanning tree of weight sixteen. The first greedy edge is absent from . Adding it creates the triangle on vertices ; remove to obtain a tree of weight eighteen containing . The second greedy edge is already present. Finally, add to this new tree; the resulting cycle contains , whose smaller weight permits its removal. The final tree has weight nineteen. The exchange witnesses here are explicit edges, whereas the general theorem obtains one from augmentation without assuming a graph.
A rejected edge can have greater weight than a later accepted edge: has weight six, but has weight four. This is not a contradiction. Accepting an edge depends on the entire previously chosen forest, not on weight alone. In particular, adding after and would violate independence, while joins two components.
Greedy stops being optimal, although the problem stays tractable for two matroids.
A path to generalization
What if a set must be independent in two matroids?
Greedy stops being optimal, although the problem stays tractable for two matroids.
Bipartite matching is the common independent sets of two partition matroids: at most one edge at each left vertex, and at most one at each right vertex. With edges of weight , and , of weight , greedy takes and stops at , but the other two edges give . For two matroids, polynomial-time algorithms for the maximum common independent set are known; for three, the problem is NP-hard.
Summary
Augmentation lets an independent greedy choice replace an element of an optimum base. The scan order ensures the replacement is no lighter. Repeating the exchange gives a maximum-weight base for any real weights.
Exercises
Quick check
(In the rank-two cardinality matroid on four elements with weights , list two possible greedy outputs and their common weight.)
Process the elements in the scan order and check the rank after each step.
Solution · Answer
Greedy must take the weight-six element. Either of the tied weight-four elements may come next, producing two distinct bases, each of weight . The negative element cannot be included after the rank is filled.
Quick check
(In the four-vertex graphic example, start with the tree . Add and name an edge that can be removed to give a tree containing and . Compare the old and new weights.)
Adding an edge to a tree creates exactly one cycle.
Solution · Answer
Adding creates the cycle . Remove to obtain . The original weight is and the new weight is . The unchanged edge still attaches vertex .
Quick check
(The independent sets of a hereditary family are precisely the subsets of and the subsets of . Exhibit a failed augmentation and choose positive weights for which descending greedy is suboptimal.)
Look for an independent set that no element of a larger independent set can extend.
Solution · Answer
Take and ; neither element of can be added to . Give weight and give each of weight . Greedy obtains , but has weight .
Quick check
(In a rank-two cardinality matroid on elements of weights , give both the maximum-weight base and the maximum-weight independent set. Explain why the objectives differ.)
A base must be maximal; an independent set may stop earlier.
Solution · Answer
The heaviest base contains the weights and , totaling . The best independent set is the singleton of weight . A base must be maximal and therefore has two elements, whereas an arbitrary independent set may stop earlier.