1
$\begingroup$

Here's the proof: http://www.cs.cornell.edu/courses/CS6820/2014fa/matchingNotes.pdf

What I don't understand is why "For an edge f there can be f(e) for up to at most two edges e, conflicting with edge f at the two different ends."

$\endgroup$

1 Answer 1

1
$\begingroup$

The notes aren't so clear (also the inequalities below should go the other way).

The proof is this. If $e$ is in a max-weight matching, and $e$ is not in our greedy matching, then this must be because at least one of $e$'s endpoints is part of some other edge in the greedy matching. Because that other edge is in the matching, it contributes at least $w_e$, otherwise we would have chosen $e$ instead in our greedy algorithm.

So the total weight in the optimal matching and not in the greedy one, by summing $w_e$, is at least the total weight of all of these edges in the greedy matching. The catch is that we could have counted each edge in the greedy matching up to two times. (Maybe its left endpoint was touching some $e_1$ in the optimal matching, and its right endpoint was touching some $e_2$ in the optimal matching.)

So we have shown that $2*$(greedy matching) $\geq$ (optimal matching).

$\endgroup$
1
  • $\begingroup$ Nice, thank you for taking the time to "repair" the notes - they include many mistakes and unclarities. $\endgroup$ Feb 13, 2015 at 15:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .