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 $G$reedy.2011-07-06

1 Answers 1

2

Your argument makes no sense.

(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.

(2) The second part deals with equal weights. It suffers from the same problem, and moreover in arguments involving matroids you never argue that way. There is only one case and the argument is going to work even if weights are identical.

(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.

  • 0
    I'll follow your advice. Maybe it will help, thanks!2011-07-07