# polynomial time approximation algorithm problem

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.

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.
• 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. Nov 18, 2021 at 22:31