Description: The traveling salesman problem (TSP) is to find the shortest hamiltonian cycle in a graph.
The graph nodes represents cities and the edges represents road between those cities.
The problem was first formulated as a mathematical problem in 1930 and is one of the most intensively studied problems in optimization.

Applications: The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as genome sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. In many applications, additional constraints such as limited resources or time windows make the problem considerably harder.

Algorithmic problem:
Input - graph(V,E)
Output - Vopt, an ordered list of nodes (cities)

Algorithmic Solutions:

1) Since TSP is an NP-hard problem, yet it is a computable problem the brute force solution will output the optimal solution yet it will be super slow.

2) Approximation algorithm - The best approximation algorithm stated is that of Sanjeev Arora . The algorithm guarantees a (1+1/c)-approximation for every c > 1. It is based om geometric partitioning and quad trees.

3) Devising "suboptimal" or heuristic algorithms, i.e., algorithms that deliver either seemingly or probably good solutions, but which could not be proved to be optimal.
The best known algorithm which used heuristics called "tour construction", Tour construction algorithms have one thing in commmon,
they stop when a solution is found and never tries to improve it. The best tour construction algorithms usually gets within 10-15% of optimality.

1) Nearest Neighbor
2) Greedy
3) Insertion Heuristics
4) Most heuristics can only guarante a worst-case ratio of 2 (i.e. a tour with twice the length of the optimal tour). Professor Nicos Christofides extended one of these algorithms and concluded that the worst-case ratio of that extended algorithm was 3/2. This algorithm is commonly known as Christofides heuristic.

external image optimap_tsp_solver.jpg
Reference: Heuristics for the Traveling Salesman Problem by Christian Nilsson