Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
The algorithm is usually just called Greedy. –  Yuval Filmus Jul 6 '11 at 6:01

1 Answer 1

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.

share|improve this answer
    
First of all, thank you for your answer. Would be so kind and explain to me your point (3) more detailed? Unfortunately I don't get the idea. Thanks! –  Aufwind Jul 7 '11 at 1:03
    
Since this is homework, I prefer not to spell out the solution. For a further hint, look again at the proof that greedy is optimal for a maximum weight independent set. –  Yuval Filmus Jul 7 '11 at 5:38
    
I'll follow your advice. Maybe it will help, thanks! –  Aufwind Jul 7 '11 at 6:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.