1
$\begingroup$

Input: number of edges and vertices, and array of all edges in graph.

Output: array of edges that construct a matching, so that: $$\frac{\text{the number of edges in this matching}}{\text{the number of edges in maximum matching}} \geq \frac{1}{2}$$


Algorithm I implemented

Loop:

  • take a random edge (actually in order it was given);
  • if we can add it to our matching then add;

Finally we get a matching.

The proof of condition from given section by contradiction: let's compare our matching with the maximum one. Let's consider one edge from our matching. There're two cases: the same edge is in the maximum matching or not. If it belongs to the maximum then it's OK. If not, then there's could be not more than two adjacent edges in maximum matching. Let's assume that it happened with each edge in our matching. Nevertheless, our matching satisfies the given conditions: it has not less than 0.5 of number of edges in maximum matching.

However the proof seems not really good to me. I guess there also should be a proof by induction by edges of matching. But I can't come up with a good idea.

$\endgroup$
  • $\begingroup$ You want to proof that your greedy algorithm is a 2-approximation. In my opinion your proof goes in the right direction. Maybe will become clearer if you formalize your proof. $\endgroup$ – dtt Oct 21 '16 at 14:49
  • $\begingroup$ cs.stackexchange.com/q/64650/755 $\endgroup$ – D.W. Oct 21 '16 at 17:01
  • $\begingroup$ Your algorithm doesn't seem to terminate. Do you sample with or without replacement? $\endgroup$ – Raphael Oct 22 '16 at 7:50
1
$\begingroup$

Let $M$ be a maximal matching in the graph $G$. Let $M'$ be the matching returned by our approximation algorithm (obviously this algorithm returns a valid matching).

For all $e\in M'$ let $M_e\subseteq M$ be the set of edges in $M$ who have common vertices with $e$, meaning all $e_M\in M$ such that $e_M\cap e\neq\emptyset$. Obviously $\forall e\in M': |M_e|\le 2$, since at the worst, $e=(u,v)$ and both $u,v$ are matched to some other vertex in $M$.

Note that $M=\bigcup\limits_{e\in M'}M_e$. To see why, suppose for the purpose of contradiction that there exists $e\in M$ with no common vertices with any $e'\in M'$. This means that our algorithm could have added $e$ to $M'$, contradiction. So we have:

$|M|\le\sum\limits_{e\in M'}|M_e|\le 2|M'|$.

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