The traveling salesman problem is stated in simple terms: given an arrangement of cities, and traveling distances between pairs of cities, what is the shortest possible path to travel between all such cities? It appears deceptively simple yet, from a computational standpoint, is extremely inefficient to exhaustively solve. According to the “naive solution”, the most inefficient solution, the problem is only solved by trying every possible path between all possible sequences of cities, and then selecting the path with the shortest total length amongst them. This solution has expensive computational costs in the order of .
Christofides algorithm was considered the most efficient approximation until a recent 2020 algorithm utilizing random generation was released.