Matroid Theory + Greedy, in depth: testing whether your greedy is safe, laminar caps, crossing constraints and sensitivity ranges

The theorem as a contract

State the theorem as a contract with two clauses. Let E be a finite set of items and F a family of feasible subsets that contains the empty set and is closed under removing items. The greedy considers items in descending weight and adds each one if the result is still feasible.

1. If F is a matroid, the greedy returns a maximum-weight feasible set for every weight vector. Stop at the first non-positive weight to get the best feasible set, or keep going to get the best maximal set (a basis).
2. If F is not a matroid, there is some weight vector for which the greedy is wrong. This is the converse, due to Rado and Edmonds. It is constructive: a pair of feasible sets A and B with |A| greater than |B| where nothing in A extends B becomes a losing instance when B's items get slightly higher weights than A's.

The second clause is the useful one in practice. Testing on today's weights tells you nothing about tomorrow's. If the constraint family fails the augmentation rule, some future weighting will break the greedy, and the question is only when.

Two corollaries are worth writing on the wall. First, the greedy reads weights only through comparisons, so the basis it returns is unchanged by any strictly increasing transform. Replacing w with w cubed or with its rank gives the same basis; cubing the weights of the spanning-tree example later in this article reproduces the same tree. For the best-feasible-set variant, which stops at the first non-positive weight, the transform must also keep positive weights positive, so log w is unsafe there. Second, because the result is optimal for every weighting consistent with the same order, it is also optimal for bottleneck objectives. A minimum spanning tree minimises the heaviest edge among all spanning trees, not just the sum. That is why one sort serves cost minimisation, worst-link minimisation and lexicographic tie-breaking at the same time.

Checking your constraints before trusting the greedy

Brute force is the right first tool. Real constraint sets are usually small combinations of counters and caps, and an exhaustive check on eight or ten items finds violations of the axioms quickly. The checker below enumerates the feasible family and reports the first rule it breaks, with a witness.

import itertools

def check_matroid(ground, feasible):
    """Return None if feasible() defines a matroid on ground, else a witness."""
    fam = {frozenset(S) for r in range(len(ground) + 1)
           for S in itertools.combinations(ground, r) if feasible(list(S))}
    if frozenset() not in fam:
        return ("empty set infeasible",)
    for S in fam:                                   # hereditary rule
        for x in S:
            if S - {x} not in fam:
                return ("hereditary", S, x)
    for A in fam:                                   # augmentation rule
        for B in fam:
            if len(A) > len(B) and not any(B | {x} in fam for x in A - B):
                return ("augmentation", A, B)
    return None

Pair it with a property test that compares the greedy with exhaustive search on random weights. The two tests catch different mistakes: the axiom check catches a wrong model of the constraints, and the property test catches a wrong oracle implementation. On random eight-item instances, 2,000 trials each, a family with per-brand caps of 2 and a total cap of 4 had the greedy optimal in all 2,000 trials. A family with a cap of 1 per brand and also 1 per colour had the greedy suboptimal in 615 of 2,000 trials, with a worst case of 0.524 of the optimum.

The checker is exponential, so run it in a unit test on small instances drawn from the same rules as production, never on production data itself.

Worked example: nested caps in a ranking carousel

A ranking service must pick 4 products for a carousel. Products belong to product lines, and lines belong to brands. Business rules: at most 1 product per line, at most 2 per brand, 4 in total. The cap groups are nested (every line sits inside one brand, and every brand inside the whole), so they form a laminar family, and a laminar family of caps is a matroid. The greedy is therefore exact.

The greedy picks r1, w1, b1 and c1 with total 32.7, and exhaustive search over all subsets returns the same set. The oracle is a counter per group plus a walk up the nesting chain:

class LaminarOracle:
    def __init__(self, parent, cap):
        self.parent, self.cap = parent, cap        # group -> parent group, group -> cap
        self.used = {g: 0 for g in cap}

    def chain(self, group):
        while group is not None:
            yield group
            group = self.parent.get(group)

    def can_add(self, group):                      # group = the item's innermost group
        return all(self.used[g] < self.cap[g] for g in self.chain(group))

    def add(self, group):
        for g in self.chain(group):
            self.used[g] += 1

Each query costs the depth of the nesting, here 3. Log the first full group in the chain on every rejection. That one string answers the question product owners always ask: why was this item not shown?

When caps cross: what the greedy still guarantees

Now add a rule that cuts across the hierarchy: at most 1 product per colour as well as 1 per brand. Brand caps and colour caps are each a partition matroid, but their intersection is not a matroid, and the checker immediately returns an augmentation witness. With items x (brand A, red, score 10), y (brand A, blue, 9) and z (brand B, red, 9), the greedy takes x and then cannot take either of the others, scoring 10, while y plus z scores 18.

What survives is an approximation guarantee. On the intersection of k matroids, the greedy always reaches at least 1/k of the optimum. With two crossing cap families that is one half, and the measured worst case of 0.524 sits just above it. You have three options:

• Accept the half. Often fine for ranking, where scores are noisy anyway. Monitor the gap on a sample with exhaustive search or an integer program.
• Solve it exactly. Two matroids admit weighted matroid intersection in polynomial time. For two partition matroids this is a bipartite assignment problem, and an off-the-shelf assignment solver is the practical route.
• Restructure the rule. If colour can be nested inside brand, the family becomes laminar again. Ask whether the business really needs the crossing rule before buying the heavier algorithm.

Sensitivity ranges from fundamental circuits

Once a greedy answer is in production, the next question is how stable it is. Matroids give an exact answer through fundamental circuits. Take the minimum-weight basis B (for graphs, the minimum spanning tree).

• A rejected item e has a fundamental circuit: e plus the unique set of basis items it depends on. e stays out as long as its weight is at least the maximum weight on that circuit. Lower it below that and it swaps in for the heaviest circuit member.
• A chosen item f stays in as long as its weight is at most the minimum weight among the rejected items whose fundamental circuits contain f. That set is the fundamental cocircuit of f.

In the example, rejected edge QS (weight 10) has fundamental circuit PQ, PR, RT, TU, SU, whose heaviest member is TU at 6, so QS stays out for any weight of 6 or more. Tree edge RT (weight 3) appears only in the circuit of QS, so it stays in up to 10. Tree edge PQ appears in the circuits of QR (5) and QS (10), so its limit is 5. Each range was confirmed by re-running Kruskal across a sweep of weights. At exact ties the answer depends on tie-breaking, so treat the endpoints as unstable.

def sensitivity(tree, edges, tree_path):
    """tree: set of tree edges; tree_path(u, v) -> tree edges between u and v."""
    out_limit, in_limit = {}, {e: float("inf") for e in tree}
    for e, w in edges.items():
        if e in tree:
            continue
        circuit = tree_path(*e)
        out_limit[e] = max(edges[f] for f in circuit)    # e stays out while w >= this
        for f in circuit:
            in_limit[f] = min(in_limit[f], w)            # f stays in while w <= this
    return out_limit, in_limit

This version walks each path, so it costs O(n) per rejected edge. For large graphs, binary lifting answers each path maximum in O(log n), and the in-limits can be filled by taking rejected edges in increasing weight and skipping already-labelled tree edges with a union-find. The output tells you which weight changes are free (no recompute) and which edges are fragile, which is the same information an LP sensitivity report gives.

Operational guidance

• Make ties deterministic. Sort by (weight, stable id). Optimality holds for any tie order, but different runs choosing different optimal sets break caches, diffs and A/B comparisons.
• Recompute only when a range is crossed. Store each item's sensitivity limit. A weight update inside its range needs no recompute; one outside triggers a single swap along a circuit, or a rebuild if many cross at once.
• Log the binding constraint. For a laminar oracle, the first full group; for a graphic oracle, the fundamental circuit. It is cheap to record and it explains every rejection.
• Keep the checker in CI. When a product manager adds a rule, the axiom test on small generated instances fails before the greedy silently becomes a heuristic.
• Mind the variant you need. Best feasible set and best basis differ when weights can be negative. A carousel that must have exactly 4 slots filled is a basis problem; one that may show fewer is not.

Failure modes

• A new rule breaks augmentation. Crossing caps, a budget on total price or a pairwise conflict list. The greedy keeps running and the loss is invisible until someone compares against an exact solver.
• Oracle state leaks between runs. Reusing a counter or union-find object silently forces the previous run's picks into this run.
• Floating-point weights with near ties. The set flips between runs when weights differ in the last bits. Quantise, or tie-break by id.
• Ranges read at the wrong end. The rules above are for a minimum-weight basis. For a maximum-weight basis, reverse every inequality.
• Using the checker on large inputs. It is exponential by design. Use it on generated instances of 8 to 12 items only.

Trade-offs

What to do next

1. List every constraint on your selection problem and mark which ones nest.
2. Run the axiom checker on generated eight-item instances of those rules.
3. If it passes, add a greedy-versus-brute-force property test to CI next to it.
4. If it fails, measure the gap on a sample and choose between accepting it, solving exactly and restructuring the rule.
5. Compute sensitivity ranges for the production answer and use them to skip unnecessary recomputes.
6. Read Kruskal's MST deep dive for the graphic case at scale and Greedy Algorithms, in depth for exchange arguments outside matroids.