Traveling Salesman Problem

URI: https://gptkb.org/entity/Traveling_Salesman_Problem

GPTKB entity

Statements (58)

Predicate	Object
gptkbp:instanceOf	gptkb:Combinatorial_Optimization_Problem
gptkbp:abbreviation	gptkb:TSP
gptkbp:application	gptkb:Logistics Astronomy Manufacturing Genetics Microchip Design
gptkbp:complexity	gptkb:NP-hard
gptkbp:definedIn	Given a list of cities and the distances between each pair, find the shortest possible route that visits each city exactly once and returns to the origin city.
gptkbp:famousInstance	Dantzig–Fulkerson–Johnson instance
gptkbp:field	gptkb:Mathematics Computer Science Operations Research
gptkbp:formedBy	gptkb:19th_century
gptkbp:hasApproximationRatio	1.5 (Christofides Algorithm for metric TSP)
gptkbp:hasAsymmetricVersion	gptkb:Asymmetric_TSP
gptkbp:hasPolynomialTimeSolution	No (for general case) Yes (for some special cases)
gptkbp:hasSymmetricVersion	Symmetric TSP
gptkbp:isOpenProblem	Yes (no polynomial-time algorithm known for general case)
gptkbp:notableFor	gptkb:Concorde_TSP_Solver gptkb:Dynamic_Programming gptkb:Branch_and_Bound Christofides Algorithm Nearest Neighbor Algorithm
gptkbp:relatedTo	gptkb:Vehicle_Routing_Problem Assignment Problem Chinese Postman Problem Hamiltonian Cycle Problem
gptkbp:solvedBy	gptkb:Heuristic_Algorithms Approximation Algorithms Exact Algorithms
gptkbp:studiedBy	gptkb:George_Dantzig gptkb:Richard_Karp gptkb:Richard_M._Karp gptkb:Michael_Held gptkb:Selmer_Johnson Ralph Fulkerson
gptkbp:usedIn	gptkb:robot Astronomy Manufacturing Scheduling Network Design Data Clustering Route Planning Circuit Design Genome Sequencing Logistics Optimization
gptkbp:bfsParent	gptkb:Hamiltonian_Cycle gptkb:Traveling_Salesman_Problem_(decision_version) gptkb:TSPLIB gptkb:Shortest_Path_Problem gptkb:Hamiltonian_Graph gptkb:Undirected_Hamiltonian_Cycle gptkb:Undirected_Hamiltonian_Path gptkb:TSP
gptkbp:bfsLayer	7
https://www.w3.org/2000/01/rdf-schema#label	Traveling Salesman Problem