Advanced Greedy Correctness and Matroids

Matroids formalize a family of independence constraints under which weight-ordered greedy is always correct. They explain why forest-edge selection supports Kruskal and why superficially similar independence systems may fail. This introductory lesson states the axioms and weighted-basis theorem, then implements a partition matroid: select items subject to per-category quotas, maximizing the weight of a basis. Specialized greedy algorithms need not all be matroid instances.

Prerequisites: Greedy Proofs; MST cut/exchange arguments; sets and independence. Related existing lessons: Minimum spanning tree.

Build the idea

1. Define independence and bases

   A matroid is a finite ground set E with a nonempty family I of independent subsets. Heredity says every subset of an independent set is independent. Augmentation says if independent A,B have |A|<|B|, some element of B−A can be added to A while remaining independent. A basis is a maximal independent set. Augmentation implies all bases have the same size, the rank; maximal does not automatically mean maximum weight.

2. Apply weighted greedy

   For a maximum-weight basis, sort elements by descending weight and add one whenever independence is preserved, continuing through all elements. Negative weights are included when necessary to complete a basis. If instead maximizing weight over arbitrary independent sets, negative elements may be skipped; conflating these objectives produces wrong answers. A graphic matroid takes edges as elements and forests as independent sets, making minimum-weight bases correspond to spanning forests with ascending weight.

3. Correctness proof: extend an optimal basis

   Let greedy prefix P lie in an optimal basis O. When greedy adds g outside O, the matroid exchange consequence for adding g to O supplies an element e∈O−P that can be removed while keeping a basis containing P+g. Because P+e is independent, e could not have been rejected earlier in the sorted scan while outside P; heredity would have made it feasible then. Thus weight(g)≥weight(e), and replacing e does not lower optimum weight. Induction builds an optimal basis matching greedy. The exchange consequence follows by extending independent sets with augmentation, not from heredity alone.

4. Partition example and sample

   Items are grouped into categories with capacities qc. Independence means taking at most qc from each category. If |A|<|B|, some category has fewer A items than B items; adding a B item from that category preserves its quota, proving augmentation. With quotas [1,2] and items (1,10),(1,9),(2,8),(2,−1),(2,−5), greedy selects IDs 1,3,4 for rank 3 and weight 17. Skipping every negative would give weight 18 but only two items, not a basis.

5. A hereditary system where greedy fails

   Matchings are hereditary but not generally a matroid. On a three-edge path, let the middle edge have weight 3 and outer edges weight 2 each. Greedy takes the middle for weight 3, while the two disjoint outer edges give 4. The one-edge matching {middle} cannot be augmented by either edge from {outer,outer}, violating augmentation. This exact missing axiom explains the failure instead of blaming tie-breaking. Interval, fractional and leaf-based greedy proofs may use other structures and do not become matroids just because they are greedy.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
struct Item{
    int category,id;
    long long weight;
};
int main(){
    int n,m;
    std::cin>>n>>m;
    std::vector<int>capacity(m+1),used(m+1);
    for(int c=1;c<=m;++c){
        std::cin>>capacity[c];
    }
    std::vector<Item>items(n);
    for(int i=0;i<n;++i){
        std::cin>>items[i].category>>items[i].weight;
        items[i].id=i+1;
    }
    std::sort(items.begin(),items.end(),[](Item a,Item b){
        return a.weight!=b.weight?a.weight>b.weight:a.id<b.id;
    });
    long long total=0;
    std::vector<int>basis;
    for(Item a:items){
        if(used[a.category]<capacity[a.category]){
            ++used[a.category];
            total+=a.weight;
            basis.push_back(a.id);
        } // Include negative weights too: optimize a BASIS, not an arbitrary independent set.
    }
    std::sort(basis.begin(),basis.end());
    std::cout<<basis.size()<<' '<<total<<'\n';
    for(int i=0;i<(int)basis.size();++i){
        std::cout<<basis[i]<<(i+1==(int)basis.size()?'\n':' ');
    }
    if(basis.empty()){
        std::cout<<'\n';
    }
}

Complexity analysis

O(n log n+m) time: sorting dominates, and each partition-independence test is O(1). O(n+m) storage. A general matroid implementation’s cost also includes its independence oracle, which need not be constant. Weight magnitude≤10^14 fits long long.

Example input and output

Read n m (0≤n≤100000, 1≤m≤100000), then m nonnegative capacities≤n, then n category weight rows (category 1..m, weight within ±10^9). Print maximum-weight basis size/weight and selected IDs in increasing order. Rank is Σ min(quota,available category count).

Input

5 2
1 2
1 10
1 9
2 8
2 -1
2 -5

Output

3 17
1 3 4

A basis must fill both available category-2 slots, so the less-negative item −1 is included with weights 10 and 8.

Practical applications

Use the theorem to recognize weighted forest and quota-selection structures and to diagnose missing exchange properties. It is a broad mathematical guarantee, not a replacement for proving specialized scheduling or lexical feasibility arguments. More advanced matroid intersection needs algorithms beyond a single greedy scan.

Check your understanding

Which missing property defeats weight-first greedy for matchings?

Put it into practice

Enumerate quota-feasible subsets and compare only those having full rank.