How can we actually define a polynomial-time 4-approximation algorithm for vertex cover or knapsack problem?

For say we have 2 approximation problems which less than equal 2C*. But when we have a larger or 4 approximation sizes how we can derive it.


1 Answer 1


For vertex cover: start with an empty vertex cover $S$. Iteratively consider the edges of the graph. For each edge $e=(u,v)$, check if $\{u,v\} \cap S = \emptyset$. If that's the case we say that $e$ is special and we add both $u$ and $v$ to $S$.

At the end of the algorithm $S$ is a vertex cover containing at most twice as many vertices as a minimum vertex cover. To see that that's the case notice that special edges form a matching, that $|S|$ is twice the number of special edges, and that all vertex covers must contain at least one endpoint of each special edge.

  • $\begingroup$ well, then what does 4 approximation actually do? its not optimal one right. but whats the purpose of using 4 approximation algorithm>? $\endgroup$
    – JCybersec
    Nov 18, 2021 at 22:04
  • $\begingroup$ Whats the purpose of using a 4-approximation algorithm? I don't know... especially for vertex cover where a $2$-apx can be found in linear time. Maybe you can find some clues where you encountered this task. In general an algorithm with a higher approximation ratio might be more desirable, e.g., if it's faster than another approximation algorithm with a smaller approximation ratio. $\endgroup$
    – Steven
    Nov 18, 2021 at 22:31
  • $\begingroup$ I found this in a research article and they used 4 approximation algorithm ideas, but I am not sure how this operation works for string transformation. $\endgroup$
    – JCybersec
    Nov 18, 2021 at 23:57

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.