Traveling Salesman Problem (optimization version)
GPTKB entity
Statements (50)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
mathematical optimization
NP-hard problem |
| gptkbp:application |
logistics
manufacturing DNA sequencing circuit design route planning drilling optimization |
| gptkbp:approximationRatio |
Christofides' algorithm guarantees 1.5 approximation for metric TSP
|
| gptkbp:category |
gptkb:mathematical_concept
gptkb:NP-hard_problems optimization graph theory algorithmic problem operations research problem routing problems |
| gptkbp:complexity |
gptkb:NP-hard
|
| gptkbp:famousInstance |
gptkb:TSPLIB
ATT48 |
| gptkbp:field |
gptkb:mathematics
computer science operations research |
| gptkbp:formedBy |
1930s
|
| gptkbp:goal |
find the shortest possible route that visits each city exactly once and returns to the origin city
|
| gptkbp:hasAsymmetricVersion |
Asymmetric Traveling Salesman Problem
|
| gptkbp:hasSymmetricVersion |
Symmetric Traveling Salesman Problem
|
| gptkbp:hasVersion |
gptkb:Traveling_Salesman_Problem_(decision_version)
|
| https://www.w3.org/2000/01/rdf-schema#label |
Traveling Salesman Problem (optimization version)
|
| gptkbp:input |
distances between each pair of cities
list of cities |
| gptkbp:namedAfter |
traveling salesman
|
| gptkbp:notableFor |
Christofides' algorithm
Held-Karp algorithm |
| gptkbp:openProblem |
no polynomial-time algorithm known for general case
|
| gptkbp:output |
minimum total distance
optimal tour |
| gptkbp:relatedTo |
gptkb:Hamiltonian_cycle_problem
gptkb:vehicle_routing_problem assignment problem |
| gptkbp:solvedBy |
gptkb:simulated_annealing
gptkb:genetic_algorithms gptkb:integer_linear_programming dynamic programming heuristics approximation algorithms branch and bound exact algorithms ant colony optimization |
| gptkbp:bfsParent |
gptkb:Traveling_Salesman_Problem_(decision_version)
|
| gptkbp:bfsLayer |
7
|