Q61.Marks: +2.0UGC NET Paper 2: Computer Science 8th Oct 2022
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?
1.Statement I true and Statement II false
2.Statement I and Statement II true✓ Correct
3.Statement I false and Statement II true
4.Statement I and Statement II false
Solution
The correct answer is Option 2
Explanation:
An approximation algorithm is a way of dealing with NP-completeness for an optimization problem. This technique does not guarantee the best solution.
The goal of the approximation algorithm is to come as close as possible to the optimal solution in polynomial time.
Such algorithms are called approximation algorithms or heuristic algorithms.
A vertex cover of an undirected graph is a subset of its vertices such that for every edge (u, v) of the graph, either ‘u’ or ‘v’ is in the vertex cover. Although the name is Vertex Cover, the set covers all edges of the given graph.
Vertex Cover Problem is a known NP Complete problem, there is no polynomial-time solution for this unless P = NP.
There are approximate polynomial-time algorithms to solve the problem 2-approximation for vertex cover via greedy matchings.
2 - approximation for vertex cover via LP rounding.
Greedy O(log n) approximation for set-cover.
Approximation algorithms for MAX-SAT.
The traveling salesman problem is NP-complete.
The TSP problem is NP-complete even if we require the cost function to satisfy the triangle inequality.