Given a weighted, undirected, bipartite, graph $G(V,E)$. All edge weights are assumed to be non-negative. Let $d(u)$ be the degree of vertex u. Let $c(u,v)$ be the cost of edge $(u,v)$. Goal: compute a maximum weight bipartite matching.

A common 2-approximation algorithm to compute a maximum weight matching $M$ is the following:

While $E$ is non-empty:

- remove the heaviest edge $(u,v)$ from $E$ and add it to $M$
- remove all edges incident to $u$ and $v$ from $E$

An alternative algorithm which often (not always) produces a matching of higher quality would be the following:

While $E$ is non-empty:

- remove the edge $(u,v)$ from $E$ which maximizes $\frac{c(u,v)}{d(u)+d(v)}$ and add it to M
- remove all edges incident to u and v from E

Is this modified greedy algorithm still a 2-approximation?