Statement I: Vertex cover has a polynomial-time 2-approximation algorithm. Statement II: TSP-tour is a polynomial-time 3-approximation algorithm for the travelling salesman problem with the triangle inequality. Which is correct?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. Statement I true and Statement II false
Explanation
APPROX-VERTEX-COVER is a 2-approximation. APPROX-TSP-TOUR (MST-based) with the triangle inequality is a 2-approximation, not 3.
More Data Structures and Algorithms questions
- The postfix form of the expression (A + B) * (C * D - E ) * F /G is _______
- A double‐ended queue (dequeue) supports adding and removing items from both the ends of the queue. The operations supported by dequeue are…
- Two balanced binary trees are given with m and n elements, respectively. They can be merged into a balanced binary search tree in ____ time.
- A data structure is required for storing a set of integers such that each of the following O(log n) operations can be done in time, where n…
- Consider the following graph. Among the following sequences I. a b e g h f II. a b f e h g III. a b f h g e IV. a f g h b e Which are depth…
- Which of the given options provides the increasing order of asymptotic complexity of f1, f2, f3 f4 functions and ? f1(n) = 2n A. f2(n) = n3…