Question $4$ : $25$ points

Travelling salesman $($TSP$)$ is a famous problem in computer science due to its hardness to

solve. The problem is stated as follows: Given a list of cities along with pairwise distances

between them, what is the shortest possible route that visits each city exactly once and returns

to the origin city?

Note: DO NOT copy$/$paste answers to this problem from ChatGPT. The purpose of this

problem is to introduce you to NP$-$completeness. So$,$ please spend some time to read and think

about the topic and answer the problems with your understanding of the topic.

$($a$)[5$ points$]$ Practically, what does it mean for a problem to be NP$-$hard or NP$-$complete,

from the point of view of runtime of a possible algorithm to solve the problem? $($Hint:

does it mean that the problem is unsolvable? Or else, what does it mean?$)$

$($b$)[10$ points$]$ NP$-$hard problems are generally tackled by approximation algorithms. Answer

the following questions:

Briefly explain what is an approximation algorithms?

What is an approximation guarantee?

Considering the example of TSP$,$ what would it mean to have a $2-$approximation

algorithm for the problem?

$($c$)[10$ points$]$ Suggest a $2-$approximation algorithm for TSP in bullet points and prove its

approximation ratio to be $2.$