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 [2023/05/05 02:49] 135.181.140.36 old revision restored (2017/04/18 00:18) |
travelling_salesman_problem [2024/04/27 07:16] (current) 3.128.199.162 old revision restored (2015/10/28 11:30) |
||
|---|---|---|---|
| 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 | + | 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. |
| 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.1683269354.txt.gz · Last modified: 2023/05/05 02:49 by 135.181.140.36
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
