Problem 1 - Algorithm

Consider the traveling salesman problem where cities to be visited are placed on a plane and the distance between two cities is defined by their Euclidian distance.

1.

Show an algorithm to compute the optimal solution. Analyze its computational complexity.

2.

Show a polynomial-time approximate algorithm. Analyze the accuracy of solution.

See [AHO83] for a detailed answer.