# Journal of Advances in Applied Mathematics

### Small Traveling Salesman Problems

Download PDF (330.7 KB) PP. 101 - 107 Pub. Date: March 23, 2017

### Author(s)

**Richard H. Warren**^{*}

Retired: Lockheed Martin Corporation, King of Prussia, PA 19406, USA

### Abstract

### Keywords

### References

[1] J. Bang, J. Ryu, C. Lee, S. Yoo, J. Lim, J. Lee, A quantum heuristic algorithm for the traveling salesman problem, J. Korean Phys. Soc. 61 (2012) 1944-1949. http://link.springer.com/article/10.3938/jkps.61.1944

[2] G. Barach, H. Fort, Y. Mehlman, F. Zypman, Information in the traveling salesman problem, Applied Mathematics 3 (2012) 926-930. http://dx.doi.org/10.4236/am.2012.38138

[3] Z. Bian, F. Chudak, R. Israel, B. Lackey, W. G. Macready, A. Roy, Discrete optimization using quantum annealing on sparse Ising models. Front. Phys. 2 Article 56 (2014) 10 pages. DOI:10.3389/fphy.2014.00056

[4] H. Chen, X. Kong, B. Chong, G. Qin, X. Zhou, X. Peng, J. Du, Experimental demonstration of a quantum annealing algorithm for the traveling salesman problem in a nuclear-magnetic-resonance quantum simulator, Phys. Review A 83 (2011) 5 pages. DOI:10.1103/PhysRevA.83.032314

[5] W. J. Cook, In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press, Princeton, NJ. 2012.

[6] E. Dahl, Travelling Salesman Problem, D-Wave Systems Tutorial (Sep. 2013). Viewed Jan. 20, 2017 from http://web.archive.org/web/20130910030209/http://www.dwavesys.com/en/dev-tutorial-tsp.htm

[7] G. Gutin, A. P. Punnen (editors), The Traveling Salesman Problem and Its Variations, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2002.

[8] J. Inoue, Infinite-range transverse field Ising models and quantum computation, Eur. Phys. J. Special Topics 224 (2015) 149-161. DOI:10.1140/epjst/e2015-02348-x

[9] S. R. Kumar, T. S. Lamba, The travelling salesman cipher, Journal IETE 40 (1994) 151-154.

[10] G. Laporte, A concise guide to the traveling salesman problem, J. Operational Res. Soc. 61 (2010) 35-40. DOI:10.1057/jors.2009.76

[11] A. Lucas, Ising formulations of many NP problems. Front. Phys. 2 Article 5 (2014) 15 pages. DOI:10.3389/fphy.2014.00005

[12] R. Martoňák, G. E. Santoro, E. Tosatti, Quantum annealing of the traveling salesman problem, Phys. Rev. E 70 (2004) 5 pages. DOI:10.1103/PhysRevE.70.057701

[13] C. C. McGeoch, C. Wang, Experimental evaluation of an adiabatic quantum system for combinatorial optimization, in Proceedings of the ACM International Conference on Computing Frontiers (2013 Proceedings), Article No. 23, ACM Press, New York, 2013. DOI:10.1145/2482767.2482797

[14] H. R. Moser, The quantum mechanical solution of the traveling salesman problem, Phys. E 16 (2003) 280-285. DOI:10.1016/S1386-9477(02)00928-1

[15] G. E. Santoro, E. Tosatti, Optimization using quantum mechanics: quantum annealing through adiabatic evolution, J. Phys. A 39 (2006) R393-R431. DOI:10.1088/0305-4470/39/36/R01

[16] S. Suzuki, J. Inoue, B. K. Chakrabarti, Quantum Ising Phases and Transitions in Transverse Ising Models, 2nd edition, Lecture Notes in Physics 862, Springer, Berlin, 2013. DOI:10.1007/978-3-642-33039-1

[17] TSPLIB is a library of sample instances for the TSP available at http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf

[18] E. Tsukerman, Ping-pong and the traveling salesman problem, Experimental Mathematics, 25 (2016) 1-7. DOI: 10.1080/10586458.2014.1002140

[19] R. H. Warren, Adapting the traveling salesman problem to an adiabatic quantum computer, Quantum Inf. Process. 12 (2013) 1781-1785. DOI:10.1007/s11128-012-0490-8

[20] R. H. Warren, Special Cases of the Traveling Salesman Problem. Applied Mathematics and Computation 60 (1994) 171-177. DOI: 10.1016/0096-3003(94)90103-1

[21] R. H. Warren, Optimal Arcs for the Traveling Salesman Problem, Applied Mathematics Letters 5 (1992) 13-14. DOI: 10.1016/0893-9659(92)90028-8