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 …
Continue reading “Why the greedy algorithm of maximum weighted matching is a 2-approximation?”