Maximum-Weight Matroid Greedy Algorithm

Definition

Maximum-Weight Matroid Greedy Algorithm

Given a matroid and weights , inspect the elements of in non-increasing order of weight. Starting from , add an element precisely when the resulting set remains independent. Return the final set .

Pseudocode

    
    
    
    
        
            
            
            
        
    
    

Running time

Running time of Greedy Maximum-Weight Matroid

Greedy solves the maximum-weight matroid optimisation problem in running time

Correctness

Correctness of Greedy Maximum-Weight Matroid

Greedy solves the maximum-weight matroid optimisation problem correctly.

Correctness

Both sets are bases

Let be the greedy result in selection order. Fix an element that greedy rejects at iteration . Suppose greedy has already selected elements. Its current set is : the elements already accepted, not all elements inspected so far. Greedy rejects because .

Later iterations only add elements, so . Heredity says that a subset of an independent set is independent. For these two sets, it says

But greedy rejected , so . The contrapositive gives . No rejected element can extend ; hence is maximal.

Among all optimal solutions, choose one of largest cardinality and label its elements in descending weight order: . It is maximal too: as , an independent extension would either improve its weight or be a larger optimal solution. Both sets are bases, so exchangeability gives .

Exchange the prefixes

We want to show . Since , it suffices to compare each position:

To prove these stronger inequalities, suppose for a contradiction that one fails: for some . Stop the greedy prefix just before it selects , but take the first elements of :

The greedy prefix must be , not : including would make both prefixes size , so exchangeability would not apply. This also lets us compare adding with greedy’s later choice of .

Both prefixes are independent: and , so heredity applies. Since , exchangeability supplies some element of , with , that can be added to :

The diagram shows ; when , the marked is . The two inequalities have different sources:

The strict comparison is our temporary assumption, not a general property. Together they force greedy to inspect before selecting .

Greedy must select

Greedy inspects before it selects . If it has accepted elements at that moment, then : its current set is a prefix of . The element is only being inspected; it is not yet in .

Therefore . Heredity now gives

The set is independent, so greedy accepts as its next selection: . Here means the -th accepted element. Since is accepted later, . For example, if and , the accepted elements must occur in this order:

In general, places among , so . Exchangeability gave , a contradiction. Therefore for every , and

Since is optimal, so is .

Alternative proof by cardinality cases

Suppose is not optimal, in selection order. Among all optimal solutions, choose one of largest cardinality and label its elements in descending weight order: . Then .

Since , exchangeability gives

Because , the extension either improves on the optimal weight of or has the same weight and greater cardinality. Both contradict the choice of .

Since , exchangeability gives

Suppose greedy had selected elements when it inspected . As , heredity gives

Greedy would have selected , contradicting .

Since , some satisfies . Take the first such and set

The picture shows ; if , the circled element is .

Both prefixes are independent, and . Exchangeability supplies an index such that

The elements of are ordered by weight. Our assumed inequality at position therefore gives

Greedy inspects before selecting . Suppose it has selected elements at that moment. Since these are among the first greedy selections, . By heredity,

Greedy must select before . Thus belongs to , contradicting .

Each case contradicts the assumption. Hence is optimal.