KnowraTravelling salesman problemLinked fromLinked fromThe 17 pages that link to Travelling salesman problem, each with the reason it gives.All 17Broader topic 8Related 4Narrower topic 1Compared with 4Computational complexity theoryBroader topic: Its optimization form exemplifies problems that are hard to solve exactly at scale.Integer programmingBroader topic: Integer variables select tour edges, while constraints eliminate disconnected subtours.NP-completenessBroader topic: Its decision version is NP-complete, connecting route planning to the class.Combinatorial optimizationBroader topic: It is a defining example of selecting an optimal permutation under a global cost.NP-hardnessBroader topic: Its optimization form is NP-hard, while its decision form is NP-complete.Linear programming relaxationBroader topic: LP relaxations of tour formulations expose fractional subtours and motivate cutting planes.Mathematical problemBroader topic: It exemplifies how a clear task can become computationally difficult as its instances grow.Richard M. KarpBroader topic: Karp’s work helped establish this classic optimization problem’s NP-completeness.