The Traveling Salesman Problem and variants

The Traveling Salesman Problem (also spelled Travelling Salesman Problem, or TSP for short) asks, given a weighted graph, what is the lowest-weight cycle that visits each node exactly once. The decision problem of determining whether such a cycle exists under a given maximum weight is also known as TSP.

history | excerpt history