0
$\begingroup$

As said, I had to prove that the greedy algorithm:

  1. Initialize $C = ∅$
  2. Look for an un-covered vertex and add one of its edges to $C$
  3. Repeat 2 while there's uncovered vertices

Is a 2-approximation algorithm.

My take was:

Let's say that $OPT$ (the optimal solution) takes $k$ edges, we should prove that $ALG$ takes at most $2k$ edges.

Let's assume by contradiction that $C=2k+1$. That means that $ALG$ covers at least $2k+1$ vertices, because each edge chosen by $ALG$ covers at least one vertex. We get that $OPT$ covers at most $2k$ vertices but $ALG$ covers at least $2k+1$ which is a contradiction $⇒ C ≤ 2k$

Now that we proved that if $OPT=k$ we get that $ALG ≤2k$ we can easily show that $\frac{ALG} {OPT}≤ 2$

Is my proof correct?

$\endgroup$
1
$\begingroup$

No. Your proof would be "correct" for any constant, not only $2$ (which is a clear big red alert!).

The actual proof is as follows:

Let $OPT$ be the optimal solution, and $ALG$ the solution from this algorithm. Notice that each edge in $OPT$ connects two vertices, and thus each such edge must contribute to the covering with at most 2 vertices. Hence, the number of vertices in the graph is at most $2k$ where $k$ is the number of edges in $OPT$. Since your algorithm will take an edge for every node at the worst case, the number of edges in $ALG$ must be at most $2k$. Hence, $|ALG|\le 2\cdot |OPT|$, which means that the algorithm is indeed a 2-approximation of the problem.

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