I am trying to understand why a greedy algorithm to the maximum weight cover problem is a 2-approximation algorithm. At the moment I am having trouble understanding the analysis presented here. While I agree on the points 1.) with the caveat that the last sentence should be "Therefore, for each $e \in S^*$ that are not in $S$…" and 2.), I do not see how our set $W'$ can contain edge sets that have duplicates. Could someone walk me though it? The wikipedia article did little to improve my understanding of the problem, as I do not see the connection between the claim that each edge in $B \setminus A$ can be adjacent to at most two edges in $A \setminus B$ because A is a matching.
Maximum Weight Matching algorithm analysis
algorithmsgraph theory
Best Answer
Consider this example.
The greedy algorithm will pick edges $S=\{(0,2)$ and $(1,3)\}$ for total weight of $2$. The optimal solution is $S^* = \{(0,1), (2,3)\}$ for total weight of $17$.
In the analysis given, for each edge $e$ in $S^*$, you will pick an edge $e'$. Following the description, for $e=(0,1)$ we will pick $e'=(0,2)$, and for $e=(2,3)$ we will pick $(0,2)$ also. So $W' = \{ (0,2), (0,2) \}$. That is why $W'$ can have duplicates.
Hopefully this also shows why elements in $W'$ are only duplicated at most $2$ times. For example: suppose $W'$ contains some edge $(u, v)$. The first time it appears might be because $S^*$ contains $(u, v_1)$ for some other vertex $v_1$. The second time can be $(v, v_2)$ for some $v_2$. To appear a third time, you need either $(v, ?)$ or $(u, ?)$ in $S^*$, but either of these will contradict $S^*$ being a matching.
Lastly, your caveat about 1) is not necessary. Because if $e \in S^*$ and $e \in S$, then we can just choose $e' = e$, and the remainder of the statement still holds.