Aspire's Library

A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET

Previous Year Question (PYQs)



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.

Click Here to
View More


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More

Ask Your Question or Put Your Review.

loading...