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?

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.$