Maximum Matroid Problem

computation

Definition

Maximum Matroid Problem

Given a matroid $\mathcal{M}=(E,\mathcal{I})$ and weight function

$$\omega :E\to \mathbb{N},$$

find an independent set $I\in \mathcal{I}$ with maximum

$$\omega (I)=\sum _{e\in I}\omega (e).$$

Algorithm

$\text{Void GreedyMaximumMatroid}(\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$
$\}$

Correctness

Correctness

Greedy solves maximum matroid in time

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

Correctness

Suppose not. Let

$$S_k=\{s_1,\dots ,s_k\}\text{with}\omega (s_1)\ge \cdots \ge \omega (s_k).$$

Let $T=\{t_1,\dots ,t_q\}$ denote an optimal solution

$$\omega (t_1)\ge \cdots \ge \omega (t_q)$$

with largest cardinality. Since $S_k$ is not optimal, we infer $\omega (S_k)<\omega (T)$.

1. Case 1 ($|S_k|>|T|$): Not possible since otherwise by exchangeability property

$$\exists s_j\in S\setminus T:T\cup \{s_j\}\text{is independent},$$

a contradiction to greedy approach.

2. Case 2 ($|S_k|<|T|$): Similarly, not possible since otherwise

$$\exists t\in T\setminus S_k:S_k\cup \{t\}\text{is independent},$$

a contradiction to greedy approach.

3. Case 3 ($|S_k|=|T|$): Let $p$ be the smallest index such that $\omega (s_p)<\omega (t_p)$. Let

$$X=\{s_1,\dots ,s_{p-1}\}\text{and}Y=\{t_1,\dots ,t_p\}.$$

By exchangeability property,

$$\exists t\in Y\setminus X:X\cup \{t\}\text{is independent}.$$

Observe that $\omega (t)\ge \omega (t_p)\ge \omega (s_p)$. Consider iteration $z$ where $e_j=t$. Note that $S_z\subseteq X$. Hence

$$S_z\cup \{t\}\subseteq X\cup \{t\}.$$

By heredity,

$$S_z\cup \{t\}\text{is independent},$$

A contradiction to $t\notin S_k$.