Trace:

travelling_salesman_problem

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

Both sides previous revision Previous revision | |||

travelling_salesman_problem [2017/04/18 00:18] tramo5 |
travelling_salesman_problem [2018/10/01 13:29] (current) bsuresh old revision restored (2017/04/05 23:01) |
||
---|---|---|---|

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 [[https://www.everipedia.com/APX-complete/|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 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.1492489112.txt.gz · Last modified: 2017/04/18 00:18 by tramo5