travelling_salesman_problem
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
travelling_salesman_problem [2025/03/12 05:13] 20.171.207.155 old revision restored (2025/03/01 21:36) |
travelling_salesman_problem [2025/03/13 04:47] (current) 20.171.207.155 old revision restored (2025/03/13 04:43) |
||
|---|---|---|---|
| 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.1741770822.txt.gz ยท Last modified: 2025/03/12 05:13 by 20.171.207.155
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
