Let $(E,\mathcal{F})$ be a Matroid. Given is a Bottle-Neck-Function $b(F)=\min\{b(e)|e\in F\}$
I want to prove that the Best-In-Greedy-Algorithm maximizes every Bottle-Neck-Function over the Bases.
The Best-In-Greedy-Algorithm works like this:
- Given a weight function $c:E\to\mathbb{R}_+$ sort $E=\{e_1,\dots ,e_n\}$ such that $c(e_1)\geq\dots\geq c(e_n)$.
- Define $F:=\emptyset$.
- Iterate above (the sorted) $E$ in descending order and add $e_i$ to the set $F$ if $(F\cup\{e_i\})\in\mathcal{F}$.
If $(E, \mathcal{F})$ was only an Independent System, the algorithm would return a independent set $F\in\mathcal{F}$. Since $(E,\mathcal{F})$ is a Matroid it returns a Basis $B\in\mathcal{F}$.
So how does the Algorithm maximizes the given Bottle-Neck-function?
Let $I:=\{1,\dots ,n\}$ where $n=|E|$.
Assuming $e_i\neq e_j$ for all $i,j\in I$ with $i\neq j$. Hence there is only one possible way of sorting $E$. The Algorithm adds elements to $F$ (which is empty at first) until $F$ is a Basis. Casting $b(F)$ returns the element with minimum weight in $F$. Since there is only one way of sorting in this case, the algorithm produces the same Basis $B$ everytime it runs. Hence $b(B)=c(e_1)$ is always maximal.
Assuming, that there are $e_i = e_j$ for $i\neq j$ and $i,j\in I$ there are multiple possibilitys to sort E. (If $e_m = e_n$ both sortings $\dots \geq c(e_m)\geq c(e_n)\geq\dots$ and $\dots \geq c(e_n)\geq c(e_m)\geq\dots$ are valid. So it is possible, for the algorithm to produce (or better: detect) different Bases. For each detected Basis it is true that $b(B)=c(e_1)$ is always maximal.
Are my conclusions correct? Every suggestion is appreciated. Thank you!