Maximum-Weight Matroid Greedy Algorithm

Definition

Maximum-Weight Matroid Greedy Algorithm

Given a matroid $M=(E,\mathcal{I})$ and weights $\omega :E\to \mathbb{N}$, inspect the elements of $E$ in non-increasing order of weight. Starting from $\varnothing$, add an element precisely when the resulting set remains independent. Return the final set $S_k$.

Pseudocode

$\text{Set GreedyMaximumWeightMatroid}(\mathcal{M}=(E,\mathcal{I}),\omega )\{$
    $\text{sort elements in }E\text{ s.t. }\omega (e_1)\ge \omega (e_2)\ge \cdots \ge \omega (e_n)$
    $S_0:=\varnothing$
    $k:=0$
    $\text{foreach}j:=1\text{to}n\{$
        $\text{if}(S_k\cup \{e_j\})\text{is independent}\{$
            $k:=k+1$
            $S_k:=S_{k-1}\cup \{e_j\}$
            $s_k:=e_j$
        $\}$
    $\}$
    $\text{return}{S}_k$
$\}$

Running time

Running time of Greedy Maximum-Weight Matroid

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

$$O(|E|\cdot (\log |E|+|\mathcal{I}|\cdot |E|)).$$

Correctness

Correctness of Greedy Maximum-Weight Matroid

Greedy solves the maximum-weight matroid optimisation problem correctly.

Correctness

Both sets are bases

Let $S_k=\{s_1,\dots ,s_k\}$ be the greedy result in selection order. Fix an element $e_j$ that greedy rejects at iteration $j$. Suppose greedy has already selected $r$ elements. Its current set is $S_r=\{s_1,\dots ,s_r\}$: the elements already accepted, not all elements inspected so far. Greedy rejects $e_j$ because $S_r\cup \{e_j\}\notin \mathcal{I}$.

Later iterations only add elements, so $S_r\cup \{e_j\}\subseteq S_k\cup \{e_j\}$. Heredity says that a subset of an independent set is independent. For these two sets, it says

$$S_k\cup \{e_j\}\in \mathcal{I}⟹S_r\cup \{e_j\}\in \mathcal{I}.$$

But greedy rejected $e_j$, so $S_r\cup \{e_j\}\notin \mathcal{I}$. The contrapositive gives $S_k\cup \{e_j\}\notin \mathcal{I}$. No rejected element can extend $S_k$; hence $S_k$ is maximal.

Among all optimal solutions, choose one of largest cardinality and label its elements $T=\{t_1,\dots ,t_q\}$ in descending weight order: $\omega (t_1)\ge \cdots \ge \omega (t_q)$. It is maximal too: as $\omega \ge 0$, an independent extension would either improve its weight or be a larger optimal solution. Both sets are bases, so exchangeability gives $k=q$.

Exchange the prefixes

We want to show $\omega (S_k)\ge \omega (T)$. Since $k=q$, it suffices to compare each position:

$$\omega (s_p)\ge \omega (t_p)(1\le p\le k)⟹\omega (S_k)=\sum _{p=1}^k\omega (s_p)\ge \sum _{p=1}^k\omega (t_p)=\omega (T).$$

To prove these stronger inequalities, suppose for a contradiction that one fails: $\omega (t_p)>\omega (s_p)$ for some $p$. Stop the greedy prefix just before it selects $s_p$, but take the first $p$ elements of $T$:

$$S_{p-1}=\{s_1,\dots ,s_{p-1}\},T_p=\{t_1,\dots ,t_p\},|S_{p-1}|=p-1<p=|T_p|.$$

The greedy prefix must be $S_{p-1}$, not $S_p$: including $s_p$ would make both prefixes size $p$, so exchangeability would not apply. This also lets us compare adding $t_i$ with greedy’s later choice of $s_p$.

Both prefixes are independent: $S_{p-1}\subseteq S_k$ and $T_p\subseteq T$, so heredity applies. Since $|S_{p-1}|<|T_p|$, exchangeability supplies some element $t_i$ of $T_p\setminus S_{p-1}$, with $1\le i\le p$, that can be added to $S_{p-1}$:

$$t_i\in T_p\setminus S_{p-1}\text{and}{S}_{p-1}\cup \{t_i\}\in \mathcal{I}.$$

The diagram shows $i<p$; when $i=p$, the marked $t_i$ is $t_p$. The two inequalities have different sources:

$$\underset{i\le p,T\text{ sorted}}{\underbrace{\omega (t_i)\ge \omega (t_p)}}>\underset{\text{assumed smaller for contradiction}}{\underbrace{\omega (s_p)}}.$$

The strict comparison $\omega (t_p)>\omega (s_p)$ is our temporary assumption, not a general property. Together they force greedy to inspect $t_i$ before selecting $s_p$.

Greedy must select $t_i$

Greedy inspects $t_i$ before it selects $s_p$. If it has accepted $r$ elements at that moment, then $r<p$: its current set $S_r=\{s_1,\dots ,s_r\}$ is a prefix of $S_{p-1}=\{s_1,\dots ,s_{p-1}\}$. The element $t_i$ is only being inspected; it is not yet in $S_r$.

Therefore $S_r\subseteq S_{p-1}$. Heredity now gives

$$S_r\cup \{t_i\}\subseteq S_{p-1}\cup \{t_i\}\in \mathcal{I}⟹S_r\cup \{t_i\}\in \mathcal{I}.$$

The set $S_r\cup \{t_i\}$ is independent, so greedy accepts $t_i$ as its next selection: $s_{r+1}=t_i$. Here $s_j$ means the $j$-th accepted element. Since $s_p$ is accepted later, $r+1<p$. For example, if $r=1$ and $p=4$, the accepted elements must occur in this order:

In general, $r+1<p$ places $s_{r+1}=t_i$ among $s_1,\dots ,s_{p-1}$, so $t_i\in S_{p-1}$. Exchangeability gave $t_i\notin S_{p-1}$, a contradiction. Therefore $\omega (s_p)\ge \omega (t_p)$ for every $p$, and

$$\omega (S_k)=\sum _{p=1}^k\omega (s_p)\ge \sum _{p=1}^k\omega (t_p)=\omega (T).$$

Since $T$ is optimal, so is $S_k$.

Alternative proof by cardinality cases

Suppose $S_k=\{s_1,\dots ,s_k\}$ is not optimal, in selection order. Among all optimal solutions, choose one of largest cardinality and label its elements $T=\{t_1,\dots ,t_q\}$ in descending weight order: $\omega (t_1)\ge \cdots \ge \omega (t_q)$. Then $\omega (S_k)<\omega (T)$.

$k>q$

Since $|T|<|S_k|$, exchangeability gives

$$s\in S_k\setminus T,T\cup \{s\}\in \mathcal{I}.$$

Because $\omega (s)\ge 0$, the extension either improves on the optimal weight of $T$ or has the same weight and greater cardinality. Both contradict the choice of $T$.

$k<q$

Since $|S_k|<|T|$, exchangeability gives

$$t_i\in T\setminus S_k,S_k\cup \{t_i\}\in \mathcal{I}.$$

Suppose greedy had selected $r$ elements when it inspected $t_i$. As $S_r\subseteq S_k$, heredity gives

$$S_r\cup \{t_i\}\subseteq S_k\cup \{t_i\}\in \mathcal{I}⟹S_r\cup \{t_i\}\in \mathcal{I}.$$

Greedy would have selected $t_i$, contradicting $t_i\notin S_k$.

$k=q$

Since $\omega (T)>\omega (S_k)$, some $p$ satisfies $\omega (t_p)>\omega (s_p)$. Take the first such $p$ and set

$$S_{p-1}=\{s_1,\dots ,s_{p-1}\},T_p=\{t_1,\dots ,t_p\}.$$

The picture shows $i<p$; if $i=p$, the circled element is $t_p$.

Both prefixes are independent, and $|S_{p-1}|=p-1<p=|T_p|$. Exchangeability supplies an index $i\le p$ such that

$$t_i\in T_p\setminus S_{p-1},S_{p-1}\cup \{t_i\}\in \mathcal{I}.$$

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

$$\omega (t_i)\ge \omega (t_p)>\omega (s_p).$$

Greedy inspects $t_i$ before selecting $s_p$. Suppose it has selected $r$ elements at that moment. Since these are among the first $p-1$ greedy selections, $S_r\subseteq S_{p-1}$. By heredity,

$$S_r\cup \{t_i\}\subseteq S_{p-1}\cup \{t_i\}\in \mathcal{I}⟹S_r\cup \{t_i\}\in \mathcal{I}.$$

Greedy must select $t_i$ before $s_p$. Thus $t_i$ belongs to $S_{p-1}$, contradicting $t_i\in T_p\setminus S_{p-1}$.

Each case contradicts the assumption. Hence $S_k$ is optimal.