# Proof: BEST-IN-GREEDY-Algorithm for Matroids maximizes all Bottleneck-Functions over Bases

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!

-
The algorithm is usually just called Greedy. – Yuval Filmus Jul 6 '11 at 6:01

(1) The first part of your argument deals with the case that all weights are different. It implicitly assumes that the matroid is uniform, i.e. there is some $k$ such that a set is independent if it's of size at most $k$. In that case the proof is trivial, but a general matroid isn't uniform.
(3) The actual proof goes along the following lines. Suppose $G$ is your solution and $O$ is a better solution. Consider the situation before adding to $G$ the last (minimal weight) element. According to the exchange property of the matroid, you could then add some element of $O$, contradiction.