User Tools

Site Tools


travelling_salesman_problem

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
travelling_salesman_problem [2017/04/05 23:01]
sertalpbilal old revision restored (2015/10/28 11:30)
travelling_salesman_problem [2017/04/18 00:18] (current)
tramo5
Line 46: Line 46:
 === Complexity of approximation === === Complexity of approximation ===
  
-In the general case, finding a shortest travelling salesman tour is NPO-complete. If the distance measure is a metric and symmetric, the problem becomes APX-complete and Christofides’s algorithm approximates it within 1.5.+In the general case, finding a shortest travelling salesman tour is NPO-complete. If the distance measure is a metric and symmetric, the problem becomes ​[[https://​www.everipedia.com/​APX-complete/​|APX-complete]] ​and Christofides’s algorithm approximates it within 1.5.
  
 If the distances are restricted to 1 and 2 (but still are a metric) the approximation ratio becomes 8/7. In the asymmetric, metric case, only logarithmic performance guarantees are known, the best current algorithm achieves performance ratio $0.814 log(n)$; it is an open question if a constant factor approximation exists. If the distances are restricted to 1 and 2 (but still are a metric) the approximation ratio becomes 8/7. In the asymmetric, metric case, only logarithmic performance guarantees are known, the best current algorithm achieves performance ratio $0.814 log(n)$; it is an open question if a constant factor approximation exists.
travelling_salesman_problem.1491447704.txt.gz · Last modified: 2017/04/05 23:01 by sertalpbilal