You are using a polynomial time 2-approximation algorithm to find a tour t for the metric traveling salesman problem. Which of the following statements is true?

A. The tourt is never optimal.

B. The cost of tourt is at most twice the cost of the optimal tour.

C. The The cost of tourt is always 2 times the cost of the optimal tour.

D. The ratio of the cost of the optimal tour divided by the cost of tourt is 2.

E. All of the above

Question

Computers & Technology

Deacon Moss

9 August, 02:02

You are using a polynomial time 2-approximation algorithm to find a tour t for the metric traveling salesman problem. Which of the following statements is true?

A. The tourt is never optimal.

B. The cost of tourt is at most twice the cost of the optimal tour.

C. The The cost of tourt is always 2 times the cost of the optimal tour.

D. The ratio of the cost of the optimal tour divided by the cost of tourt is 2.

E. All of the above

+1

Answers (1)

Know the Answer?

Christine Brandt · Answer 1

B. The cost of tour t is at most twice the cost of the optimal tour.

Explanation:

You are using a polynomial time 2-approximation algorithm to find a tour t for the traveling salesman problem.

The cost of tour t is at most twice the cost of the optimal tour

The equation represented as Cost (t) < = 2 Cost (T)

Where

Cost (t) represents cost of tour t

Cost (T) represents cost of the optimal tour