Is greedy matching algorithm with normalized edge weights a 2-approximation

Question

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?

Answer 1

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).$