Traveling salesman problem (optimization version)

URI: https://gptkb.org/entity/Traveling_salesman_problem_(optimization_version)

GPTKB entity

Statements (53)

Predicate	Object
gptkbp:instanceOf	mathematical optimization
gptkbp:alsoKnownAs	TSP (optimization version)
gptkbp:application	gptkb:Logistics Manufacturing Genetics Circuit design
gptkbp:category	gptkb:Graph_theory gptkb:NP-hard_problems Optimization
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:field	gptkb:Mathematics Computer science Operations research
gptkbp:formedBy	1930s
gptkbp:generalizes	gptkb:Hamiltonian_cycle_problem
gptkbp:hasAsymmetricVersion	gptkb:Asymmetric_TSP
gptkbp:hasSpecialCase	gptkb:Vehicle_routing_problem
gptkbp:hasSymmetricVersion	Symmetric TSP
https://www.w3.org/2000/01/rdf-schema#label	Traveling salesman problem (optimization version)
gptkbp:input	Distance matrix Set of cities
gptkbp:notableContributor	gptkb:Richard_M._Karp gptkb:William_Cook gptkb:Michael_Held gptkb:David_S._Johnson gptkb:Shmuel_Winograd Applegate, Bixby, Chvátal, and Cook (Concorde TSP Solver)
gptkbp:notableFor	gptkb:Simulated_annealing gptkb:Concorde_TSP_Solver gptkb:Branch_and_bound Genetic algorithms Ant colony optimization Christofides' algorithm Dynamic programming (Held-Karp algorithm) LKH (Lin-Kernighan-Helsgaun) solver Lin-Kernighan heuristic Nearest neighbor heuristic
gptkbp:openProblem	No polynomial-time algorithm known for general case
gptkbp:output	Shortest possible tour Tour length
gptkbp:relatedTo	gptkb:Traveling_salesman_problem_(decision_version) gptkb:Chinese_postman_problem gptkb:Euclidean_TSP gptkb:Metric_TSP gptkb:Vehicle_routing_problem
gptkbp:solvedBy	Approximation algorithms Heuristic algorithms Exact algorithms
gptkbp:bfsParent	gptkb:NP-hard gptkb:NP-hardness gptkb:Traveling_salesman_problem_(decision_version)
gptkbp:bfsLayer	6