3
$\begingroup$

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!

  • 0
    The algorithm is usually just called Greedy.2011-07-06

1 Answers 1