A Tale of Revolution: Discovery and Development of TSP

Emran Islam; Mariam Sultana; Faruque Ahmed

doi:https://doi.org/10.14445/22315373/IJMTT-V57P520

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 57 | Number 2 | Year 2018 | Article Id. IJMTT-V57P520 | DOI : https://doi.org/10.14445/22315373/IJMTT-V57P520

A Tale of Revolution: Discovery and Development of TSP

Emran Islam, Mariam Sultana, Faruque Ahmed

Citation :

Emran Islam, Mariam Sultana, Faruque Ahmed, "A Tale of Revolution: Discovery and Development of TSP," International Journal of Mathematics Trends and Technology (IJMTT), vol. 57, no. 2, pp. 136-139, 2018. Crossref, https://doi.org/10.14445/22315373/IJMTT-V57P520

Abstract

In recent days combinatorial optimization problems are attracting too many researchers to spend their time after it for its high socio economic impacts and at the same time complexity in finding an exact solution. Traveling salesman problem is one of the most important and widely studied optimization problems. It has attracted a large number of researchers over the last few decades because it is simple to formulate and always it has a solution. Researchers are using TSP as a testing ground for new algorithms to solve optimization problems. Sothe importance of TSP in the field of combinatorial optimization problems is obvious. This paper reveals discovery and development of Traveling Salesman Problem.

Keywords

Graph Theory, Traveling salesman problem, combinatorial optimization

References

[1] Biggs, Norman, E. Keith Lloyd, and Robin J. Wilson. Graph Theory, 1736-1936. Oxford University Press, 1976.
[2] Knight‟s tour. In Wikipedia. Retrieved August 21, 2017, from the internet address https://en.wikipedia.org/wiki/Knight%27s_tour
[3]Wilson, R. J. "A brief history of Hamiltonian graphs." Annals of Discrete Mathematics. Vol. 41. Elsevier, 1988. 487-496.
[4] W. W. Rouse Ball, Mathematical Recreations and Problems of Past andPresent Times (later entitled Mathematical Recreations and Essays),Macmillan, London (1892).
[5] Major Jaenisch, Applications de l‟AnalyseMathdmatique au Jeu desEchecs, 3 vols., St. Petersburg (1862-63).
[6] Kirkman, Thomas Penyngton. "XVIII. On the representation of polyedra."Philosophical Transactions of the Royal Society of London 146 (1856): 413-418.
[7] W. R. Hamilton, “Memorandum respecting a new system of roots of unity,” Phil. Mag. (4) 12 (1856), 446.
[8] Biggs, Norman, E. Keith Lloyd, and Robin J. Wilson. Graph Theory, 1736-1936. Oxford University Press, 1976.
[9] L. RQdei, “EinkombinatorischerSatz,” ActaLitt. Sci. Szeged 7 (1934),39-43.]
[10]Konig, D. "Theorie der endlichenuinlunendlichenGraphen." (1936).
[11] Müller-Merbach, H. "Zweimal travelling salesman." DGOR-Bulletin 25(1983):12-13.
[12]Hahsler, Michael, and Kurt Hornik. "TSP-Infrastructure for the traveling salesperson problem." Journal of Statistical Software23.2 (2007): 1-21.
[13] Schoen, F. "Handbooks in operations research and management science: Discrete optimization." (2007): 410-410.
[14] K. Menger, Some applications of point-set methods, Annals of Mathematics (2) 32 (1931) 739–760.
[15] J.T. Robacker, Min-Max Theorems on Shortest Chains and Disjoint Cuts of a Network, Research Memorandum RM-1660, The RAND Corporation, Santa Monica, California, [12 January] 1956.
[16]www.tsp.gatech.edu/history/milestone.html
[17]Flood, M. M. "Merrill Flood (with Albert Tucker)." Interview of Merrill Flood in San Francisco on 14 (1984).
[18]Menger, Karl. "On shortest polygonal approximations to a curve." Selecta Mathematica. Springer Vienna, 2003. 81-86.
[19]A.N. Milgram, On shortest paths through a set, Reports of a Mathematical Colloquium (2) 2 (1940) 39–44.
[20]L. Fejes, €UUbereinengeometrischenSatz, MathematischeZeitschrift 46 (1940) 83–85.
[21]Few, L. "The shortest path and the shortest road through n points." Mathematika 2.2 (1955): 141-144.
[22] Beardwood, Jillian, John H. Halton, and John Michael Hammersley. "The shortest path through many points." Mathematical Proceedings of the Cambridge Philosophical Society. Vol. 55. No. 4. Cambridge University Press, 1959.
[23] P.C. Mahalanobis, A sample survey of the acreage under jute in Bengal, Sankhy6a 4 (1940) 511–530.

[24]Dantzig, George, Ray Fulkerson, and Selmer Johnson. "Solution of a large-scale traveling-salesman problem." Journal of the operations research society of America 2.4 (1954): 393-410.

[25] Schrijver, Alexander. "On the history of combinatorial optimization (till 1960)." Handbooks in operations research and management science 12 (2005): 1-68.