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 [2024/03/14 11:02]
65.21.35.251 old revision restored (2024/02/02 08:41)
travelling_salesman_problem [2024/03/14 11:02] (current)
65.21.35.251 old revision restored (2024/02/02 08:41)
Line 47: Line 47:
  
 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.
- 
- 
-Xiaolong is awesome! 
travelling_salesman_problem.txt ยท Last modified: 2024/03/14 11:02 by 65.21.35.251