Consider the following statements on approximation algorithms:
Statement I: APPROX-VERTEX-COVER is a polynomial-time 2-approximation algorithm.
Statement II: APPROX-TSP-TOUR is a polynomial-time 3-approximation algorithm for the travelling salesman problem with the triangle inequality.
Which of the following 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
CLRS proves both APPROX-VERTEX-COVER and APPROX-TSP-TOUR (MST preorder walk) are 2-approximations, so the '3-approximation' claim is wrong.More Data Structures and Algorithms questions
- Which of the following is used to determine the cost performance index?
- Software project manager is responsible for the following task: (A) Project planning (B) Project status tracking (C) Resources management (…
- Fill in the blanks: "An ________ chart is a project schedule representation that presents the project plan as a directed graph. The critica…
- Which of the following are the primary objectives of risk monitoring in software project tracking? P: To assess whether predicted risks do,…
- Which one of the following is a highly associated activity of project planning? (1) Keep track of the project progress. (2) Compare actual…
- Which of the following trees are height balanced? A. Binary Search Tree B. AVL Tree C. Red-Black Tree D. B Tree