Statements (53)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
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 |
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
|
| https://www.w3.org/2000/01/rdf-schema#label |
Traveling Salesman Problem
|
| 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:Combinatorial_Optimization
gptkb:Integer_Programming gptkb:Simulated_Annealing |
| gptkbp:bfsLayer |
6
|