User: What is the history of the travelling salesman problem throughout the years in a short bulleted list?
Assistant: * 19th century - mathematically formulated for first time by the Irish mathematician William Rowan Hamilton and by the British mathematician Thomas Kirkman
* 1930s - First studied by mathematicians in Vienna and at Harvard, most notably by Karl Menger and Merill M. Flood who was looking to solve a school bus routing problem.
* 1959 - Jillian Beardwood, J.H. Halton and John Hammersley published an article entitled "The Shortest Path Through Many Points" in the journal of the Cambridge Philosophical Society, which provided the first practical solution.
* 1960s - new approach is created, which produce a solution whose length is provably bounded by a multiple of the optimal length.
* 1972 - Richard M. Karp showed that the Hamiltonian cycle problem was NP-complete, which implies the NP-hardness of traveling salesman problem.
* 1976 - Christofides and Serdyukov independently invented new algorithm, which yields a solution that in the worst case is at most 1.5 times longer than the optimal solution.
* 1990s -  Applegate, Bixby, Chvátal, and Cook developed the program Concorde that has been used in many recent record solutions.
* 1991 - Gerhard Reinelt published the TSPLIB, a collection of benchmark instances of varying difficulty, which has been used by many research groups for comparing results
* 2006 - Cook and others computed an optimal tour through an 85,900-city instance given by a microchip layout problem, currently the largest solved TSPLIB instance.
* 2011 - Slightly improved approximation algorithm is developed for the subset of "graphical" traveling salesman problem.
* 2020 - The slightly improved approximation algorithm developed for the subset of "graphical" is extended to cover the full traveling salesman problem.