1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.