This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
travelling_salesman_problem [2023/07/02 09:14] 65.109.145.232 old revision restored (2023/07/02 02:59) |
travelling_salesman_problem [2024/04/25 14:11] 47.128.125.40 old revision restored (2024/04/21 16:23) |
||
---|---|---|---|
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! |