The Traveling Salesman Problem, TSP for short, asks for a fastest round-trip through a given set of cities. It has many obvious applications in logistics but also in other areas such as manufacturing of microchips. Solving TSP is a challenging task, as its corresponding decision problem is NP-hard, which lead to extensive research on how to efficiently compute good solutions. Some even say TSP is "one of the most celebrated and intensively studied problems in combinatorial optimization'' .
One way to solve TSP is the simple but elegant Christofides algorithm , which combines a minimum spanning tree with a perfect matching to compute a 3/2-approximate solution. This famous result, like many other solutions to TSP, requires that the distances are symmetric (travelling from city \(A\) to city \(B\) takes as much time as travelling from \(B\) to \(A\)) and satisfy the triangle inequality (travelling from \(A\) to \(C\) directly does not require more time than taking a detour through \(B\)). This may not seem like an actual restriction at first, but in reality blocked roads, one way streets or simply traffic may cause violations of symmetry.