Why the greedy algorithm of maximum weighted matching is a 2-approximation?

This post explains my understanding in a proposed greedy algorithm for the maximum weighted matching problem.

The greedy algorithm goes as follows (listed by this paper in Introduction section):

It is claimed that the greedy algorithm is a 2 approximation, i.e., greedy result >= 1/2 optimal result.

The document where the greedy algorithm is proposed is erroneous therefore the proof for the 2 approximation is unreadable. Fortunately, another guy put his words to explain it: http://math.stackexchange.com/questions/1146224/proof-for-why-maximum-weight-matching-using-greedy-guarantees-at-least-1-2-the-w. However, I think further explanation is still needed to facilitate the understanding. Here is my thoughts:

If any edge $e$ belongs to the optimal matching $M^*$ but not the greedy matching $M$ , it must be due to that at least one of its two vertices is incident on another edge $e'$ which is included in the greedy matching $M$ . Due to the greedy algorithm, $w(e') > w(e)$ otherwise the greedy algorithm could have selected $e$ . Moreover, $e' \in M \setminus M^*$ because, if $e' \in M^*$ , and we know $e \in M^*$ , then $M^*$ contains two edges incident on the same node by contradiction.

Each $e \in M^* \setminus M$ can be linked to an edge $e' \in M \setminus M^*$ where $w(e')>w(e)$ . The same edge $e'$ can be counted at most twice if traversing all $e$ (maybe one endpoint of $e'$ touches an edge $e_1 \in M^* \setminus M$ and maybe the other endpoint of $e'$ touches another edge $e_2 \in M^* \setminus M$ . ) Therefore, $\sum\limits_{e \in M^* \setminus M} w(e) < 2 * \sum\limits_{e' \in M \setminus M^*} w(e')$ . We can also obtain trivially, under the assumption that all weights are positive, that $\sum\limits_{e \in M \cap M^*} w(e) < 2 * \sum\limits_{e \in M \cap M^*} w(e)$ . Adding the two inequalities together, we get $\sum\limits_{e \in M^*} w(e) < 2 * \sum\limits_{e' \in M} w(e')$ .

The greedy algorithm is not applicable to maximum weighted perfect matching because it is not guaranteed to find perfect matching. (perfect matching: every vertex is incident on exactly one edge in the matching. ) Provided that we have the following inequalities:

optimal result for maximum weighted matching > optimal result for maximum weighted perfect matching

1/2 * optimal result for maximum weighted matching <= greedy result for maximum weighted matching

, we conclude that the greedy result for maximum weighted matching can loosely be used for maximum weighted perfect matching, if perfect matching is not strictly required. It is more appealing when the graph is a complete graph. In a complete graph, the greedy method returns a perfect matching.

The greedy algorithm takes $O(m\log m)$ to sort edge weights ( $m=|E|$ ). In a complete graph where $m=n^2$ ( $n=|V|$ ), the greedy algorithm takes $O(n^2 \log n)$ , a little better than existing $O(n^3)$ methods (such as this) to solve maximum weighted perfect matching. There is also an $1-\epsilon$ approximation method running in $O(m \epsilon^{-1} \log \epsilon^{-1})$ . However, the method is much more complicated.

Why the greedy algorithm of maximum weighted matching is a 2-approximation?

Leave a comment

Cancel reply