# Lehigh ISE / COR@L Lab Wiki

### Site Tools

travelling_salesman_problem

# Differences

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

 travelling_salesman_problem [2017/03/27 05:59]ntcnet [Computational complexity] travelling_salesman_problem [2018/10/01 13:29] (current)bsuresh old revision restored (2017/04/05 23:01) Both sides previous revision Previous revision 2018/10/01 13:29 bsuresh old revision restored (2017/04/05 23:01)2017/04/18 00:18 tramo5 2017/04/05 23:01 sertalpbilal old revision restored (2015/10/28 11:30)2017/03/27 05:59 ntcnet [Computational complexity] 2015/10/28 11:30 sertalpbilal 2015/09/22 12:58 bsuresh old revision restored (2015/09/22 12:50)2015/09/22 12:58 bsuresh deleted for testing2015/09/22 12:50 bsuresh old revision restored (2014/09/23 22:48)2015/09/22 12:49 bsuresh Minor change, added \ldots2014/09/23 22:48 sertalpbilal 2014/09/23 19:21 sertalpbilal old revision restored (2014/09/23 12:24)2014/09/23 19:20 sertalpbilal 2014/09/23 12:24 sertalpbilal created Next revision Previous revision 2018/10/01 13:29 bsuresh old revision restored (2017/04/05 23:01)2017/04/18 00:18 tramo5 2017/04/05 23:01 sertalpbilal old revision restored (2015/10/28 11:30)2017/03/27 05:59 ntcnet [Computational complexity] 2015/10/28 11:30 sertalpbilal 2015/09/22 12:58 bsuresh old revision restored (2015/09/22 12:50)2015/09/22 12:58 bsuresh deleted for testing2015/09/22 12:50 bsuresh old revision restored (2014/09/23 22:48)2015/09/22 12:49 bsuresh Minor change, added \ldots2014/09/23 22:48 sertalpbilal 2014/09/23 19:21 sertalpbilal old revision restored (2014/09/23 12:24)2014/09/23 19:20 sertalpbilal 2014/09/23 12:24 sertalpbilal created Line 41: Line 41: ===== Computing a solution ===== ===== Computing a solution ===== - ​tip​==== Computational complexity ==== + ==== Computational complexity ==== The problem has been shown to be NP-hard (more precisely, it is complete for the complexity class FPNP; see function problem), and the decision problem version ("​given the costs and a number x, decide whether there is a round-trip route cheaper than x") is NP-complete. ​ The problem has been shown to be NP-hard (more precisely, it is complete for the complexity class FPNP; see function problem), and the decision problem version ("​given the costs and a number x, decide whether there is a round-trip route cheaper than x") is NP-complete. ​ === 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 ​[[http://​www.bantayso.com|website]], the problem becomes 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.