Question Id : 18797 |
Context : UGC NET Computer Science Sep 2022 (Paper II)
Consider the following statements of approximation algorithm:
Statement I: Vertex-cover is a polynomial time 2-approximation algorithm. Statement II: TSP-tour is a polynomial time 3-approximation algorithm for travelling salesman problem with the triangle inequality. Which of the following is correct?
🎥 Video solution / Text Solution of this question is given below:
Statement I:
For the Vertex Cover problem, there is a standard polynomial time approximation algorithm.
It repeatedly chooses an edge and includes both endpoints in the vertex cover.
This gives a solution whose size is at most $2$ times the optimal solution.
So, Vertex-cover has a polynomial time $2$-approximation algorithm.
Therefore, Statement I is true.
Statement II:
For Travelling Salesman Problem with triangle inequality, the standard MST based TSP-tour approximation algorithm gives a $2$-approximation.
It does not give a $3$-approximation as the standard result.
So, the statement saying it is a polynomial time $3$-approximation algorithm is not correct in the standard form.