Statements (23)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
mathematical optimization
|
| gptkbp:Christofides_algorithm_approximation_ratio |
1.5
|
| gptkbp:edge_weights_satisfy |
gptkb:Triangle_inequality
|
| gptkbp:first_studied |
20th century
|
| gptkbp:has_approximation_algorithm |
gptkb:Christofides_algorithm
|
| gptkbp:has_polynomial-time_approximation_scheme |
No (unless P=NP)
|
| gptkbp:has_PTAS_for_special_cases |
gptkb:Euclidean_TSP
|
| gptkbp:hasApplication |
gptkb:Logistics
Operations research Routing Circuit design |
| gptkbp:hasProperty |
gptkb:Triangle_inequality
|
| https://www.w3.org/2000/01/rdf-schema#label |
Metric TSP
|
| gptkbp:input |
Complete weighted graph
|
| gptkbp:is_NP-hard |
true
|
| gptkbp:objective |
Find shortest possible tour visiting each city exactly once
|
| gptkbp:relatedTo |
gptkb:Euclidean_TSP
Symmetric TSP |
| gptkbp:studiedBy |
gptkb:Theoretical_computer_science
Operations research |
| gptkbp:variant |
gptkb:Traveling_Salesman_Problem
|
| gptkbp:bfsParent |
gptkb:Traveling_salesman_problem
|
| gptkbp:bfsLayer |
6
|