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?



Is greedy matching algorithm with normalized edge weights a 2-approximation
No, this algorithm does not always produce a matching that is within a factor 2 of the optimal matching.


Consider $G = (V,E)$ with
$$\begin{align\*} V &= \{x,y\} \uplus \{z\_1, z\_2, \dots, z\_k\}\\ E &= \{xz\_1, yz\_1, yz\_2, \dots, yz\_k\} \end{align\*}$$
and weights
$$\begin{align}w(xz\_1) &= m \\ w(yz\_1) &= M \\ w(yz\_i) &= \epsilon & i > 1 \end{align}$$
for small $\epsilon$, large $k$ and $M$, and moderate $m.$


For $M$ large enough the maximal weight matching is simply $\{yz\_1\}$ which has weight $M$.
The normalized edge weights are
$$\begin{align}w(xz\_1) &= \frac{m}{3} \\ w(yz\_1) &= \frac{M}{k+2} \\ w(yz\_i) &= \frac{\epsilon}{k+1} & i > 1 \end{align}$$
and so for large enough $k$ the algorithm will first choose $xz\_1.$
The alogrithm then removes $yz\_1$ and will choose $yz\_2$ at the next step to produce the matching $\{xz\_1, yz\_2\}$ with weight $m + \epsilon.$ We can choose $k$, $\epsilon$, $m$, and $M$ so that $M > 2(m+ \epsilon).$


