= Matroid greedy algorithm
{title2=$w(B)=\sum_{e\in B}w(e)$}
Assign each element of the finite <ground set> a <real number> $w(e)$. The <matroid greedy algorithm> sorts elements by nonincreasing weight, starts with the <empty set>, and admits an element exactly when the enlarged selection is a <matroid independent set>. Ties can be resolved arbitrarily. After all elements have been considered, the result is a <matroid basis> of maximum total weight among all <matroid bases>. This holds even with negative weights: the task is to produce a full <matroid basis>. <Matroid optimization by Michel Goemans>[Michel X. Goemans, Matroid optimization, section 5.2, pp. 5–6, greedy procedure and theorem 5.2]{ref}
Maximizing weight over all <matroid independent sets> is a different task when weights can be negative. For that task, skip negative elements; zero-weight additions are optional. With weights $w(a)=8$, $w(c)=-1$, $w(b)=-2$ in the <weighted three-vector matroid>, the heaviest <matroid basis> is $\{a,c\}$ with weight $7$, while the heaviest <matroid independent set> is $\{a\}$ with weight $8$. For nonnegative weights, every <matroid independent set> can be extended to a <matroid basis> without reducing weight, so the optimum values coincide.
\b[Proof outline.] Let $g_1,\ldots,g_r$ be the admitted elements in order, and order any competing <matroid basis> $b_1,\ldots,b_r$ by nonincreasing weight. If $w(b_k)>w(g_k)$, exchange would let one of $b_1,\ldots,b_k$ augment $\{g_1,\ldots,g_{k-1}\}$. That element was considered before $g_k$ and, by heredity, was admissible even at that earlier stage, a contradiction. Hence $w(g_k)\geq w(b_k)$ for every $k$, and summing proves optimality. Rejected elements remain inadmissible as the selection grows, by heredity, so the final selection is maximal. The guarantee depends on the <matroid independence axioms> and on weights adding independently across elements; interactions between chosen elements are a different objective.
Back to article page
