Travelling salesman problem

The optimization problem of finding a shortest closed route that visits each specified city exactly once. Its decision version asks whether a route of at most a given length exists.

Hamiltonian cycle: A cycle in a graph that visits every vertex exactly once before returning to its start. Each tour is a Hamiltonian cycle in the graph of cities and travel costs.
Graph theory: The mathematical study of vertices, edges, and the structures they form. Cities become vertices and possible journeys become edges in the standard model.
Vehicle routing problem: A family of optimization problems for designing routes that serve customers with one or more vehicles. It generalizes a single tour to fleets, demands, capacities, and service constraints.
Nearest neighbor algorithm: A greedy routing heuristic that repeatedly visits the closest unvisited city. It is fast and simple, but can produce tours far longer than optimal.
Travelling salesman problem decision version: The decision problem asking whether a tour exists whose total cost does not exceed a specified bound. This yes-or-no formulation makes the problem's NP-completeness precise.
Combinatorial optimization: The study of optimizing objectives over finite collections of discrete choices. A tour is a discrete choice of edges optimized for total travel cost.
Traveling tournament problem: A scheduling problem that arranges sports fixtures to reduce teams' travel while meeting tournament constraints. It adapts tour optimization to repeated trips constrained by a competition schedule.
Christofides algorithm: A polynomial-time algorithm that guarantees a tour no longer than 1.5 times optimal for metric instances. It offers a provable approximation where exact optimization may be impractical.
Held–Karp algorithm: A dynamic programming algorithm that solves the travelling salesman problem in O(n²2ⁿ) time. It systematically combines partial tours while avoiding repeated subproblems.
NP-hardness: A classification indicating that every problem in NP can be reduced to a given problem in polynomial time. The optimization version is NP-hard, so efficient exact algorithms are not known in general.

Linked from 17 pages