A Place for Latest Exam wise Questions, Videos, Previous Year Papers, Study Stuff for MCA Examinations - NIMCET
Previous Year Question (PYQs)
1
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?
Solution
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.
Therefore, Statement II is false.
Online Test Series, Information About Examination, Syllabus, Notification and More.