What do you think?
Rate this book
In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation
The story of one of the greatest unsolved problems in mathematics
What is the shortest possible route for a traveling salesman seeking to visit each city on a list exactly once and return to his city of origin? It sounds simple enough, yet the traveling salesman problem is one of the most intensely studied puzzles in applied mathematics―and it has defied solution to this day. In this book, William Cook takes readers on a mathematical excursion, picking up the salesman's trail in the 1800s when Irish mathematician W. R. Hamilton first defined the problem, and venturing to the furthest limits of today’s state-of-the-art attempts to solve it. He also explores its many important applications, from genome sequencing and designing computer processors to arranging music and hunting for planets.
In Pursuit of the Traveling Salesman travels to the very threshold of our understanding about the nature of complexity, and challenges you yourself to discover the solution to this captivating mathematical problem.
What is the shortest possible route for a traveling salesman seeking to visit each city on a list exactly once and return to his city of origin? It sounds simple enough, yet the traveling salesman problem is one of the most intensely studied puzzles in applied mathematics―and it has defied solution to this day. In this book, William Cook takes readers on a mathematical excursion, picking up the salesman's trail in the 1800s when Irish mathematician W. R. Hamilton first defined the problem, and venturing to the furthest limits of today’s state-of-the-art attempts to solve it. He also explores its many important applications, from genome sequencing and designing computer processors to arranging music and hunting for planets.
In Pursuit of the Traveling Salesman travels to the very threshold of our understanding about the nature of complexity, and challenges you yourself to discover the solution to this captivating mathematical problem.
248 pages, Paperback
First published January 1, 2011
46 people are currently reading
626 people want to read
About the author
William J. Cook
14 books4 followersThere is more than one author by this name on Goodreads.
William John Cook is an American operations researcher and mathematician, and Professor of Applied Mathematics and Statistics at Johns Hopkins University, where he joined the faculty in 2018. He was formerly a University Professor, Combinatorics and Optimization, University of Waterloo
See also: William J. Cook, suspense, mystery
William John Cook is an American operations researcher and mathematician, and Professor of Applied Mathematics and Statistics at Johns Hopkins University, where he joined the faculty in 2018. He was formerly a University Professor, Combinatorics and Optimization, University of Waterloo
See also: William J. Cook, suspense, mystery
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 - 26 of 26 reviews
February 4, 2017
Solving a most important problem
Solving a most important problem!
This book is for mathematicians, computer scientists, computer programmers, and geeks in general. If you are not a member of one these groups, then read no further: this book is not for you. But, if you are a member, this may be exactly what you are looking for!
The traveling salesman problem (TSP) is probably the single most important real world problem that must solved every day in many different domains. Simply said, it is a problem of trying to find the shortest possible circuit that visits all cities in a salesman area.
Sounds easy? Right?
Well, this problem is not easy! If n is number of points that must be reached, there are n factorial (n!) possible paths! For example, if there are 6 points, then there are 120 possible paths. But if there are 7 cities, then there are 5040 paths! This number grows so fast that for reasonable problems, where there are over 100 points such as in a major airline problem, no computer on the face of the earth can evaluate ever path.
Some of the domains include: scheduling aircraft by an airline, determining communication lines by a telephone server, determining the drill pattern on a printed circuit board, industrial process planning in a job shop, determining natural gas flow in a network, etc. In most cases, the problem is solved but not optimally or "best" or "least cost" manners. This book is all about trying to solve this problem to find the best possible solution!
While it is very mathematical, the book is actually in a style that is very easy to read and understand. The author is a long time researcher of the TSP. He examines the history of trying to solve the TSP ending with his own major contribution, the Concorde program which found the optimal solution of 85,900 points!
Well, is the problem solved? I am sorry to say, despite the looks at the problem by thousands of researchers including Nobel Prize winners, the answer is a hard "NO!" The problem is that the TSP is described as a NP Complete problem, one for which if one can find a polynomial time solution algorithm for, one could win the $1,000,000 Clay Millennium Prize for its solution.
This book is outstanding! It describes many of the techniques that have been tried to solve the problem and the problems that were found. For anybody trying their hand at the TSP, I would consider this book a primer, a necessary to read book.
Good luck, fellow geeks! There is at least a $1,000,000 out there waiting to reward your brilliance!
Solving a most important problem!
This book is for mathematicians, computer scientists, computer programmers, and geeks in general. If you are not a member of one these groups, then read no further: this book is not for you. But, if you are a member, this may be exactly what you are looking for!
The traveling salesman problem (TSP) is probably the single most important real world problem that must solved every day in many different domains. Simply said, it is a problem of trying to find the shortest possible circuit that visits all cities in a salesman area.
Sounds easy? Right?
Well, this problem is not easy! If n is number of points that must be reached, there are n factorial (n!) possible paths! For example, if there are 6 points, then there are 120 possible paths. But if there are 7 cities, then there are 5040 paths! This number grows so fast that for reasonable problems, where there are over 100 points such as in a major airline problem, no computer on the face of the earth can evaluate ever path.
Some of the domains include: scheduling aircraft by an airline, determining communication lines by a telephone server, determining the drill pattern on a printed circuit board, industrial process planning in a job shop, determining natural gas flow in a network, etc. In most cases, the problem is solved but not optimally or "best" or "least cost" manners. This book is all about trying to solve this problem to find the best possible solution!
While it is very mathematical, the book is actually in a style that is very easy to read and understand. The author is a long time researcher of the TSP. He examines the history of trying to solve the TSP ending with his own major contribution, the Concorde program which found the optimal solution of 85,900 points!
Well, is the problem solved? I am sorry to say, despite the looks at the problem by thousands of researchers including Nobel Prize winners, the answer is a hard "NO!" The problem is that the TSP is described as a NP Complete problem, one for which if one can find a polynomial time solution algorithm for, one could win the $1,000,000 Clay Millennium Prize for its solution.
This book is outstanding! It describes many of the techniques that have been tried to solve the problem and the problems that were found. For anybody trying their hand at the TSP, I would consider this book a primer, a necessary to read book.
Good luck, fellow geeks! There is at least a $1,000,000 out there waiting to reward your brilliance!
March 30, 2013
This is a cool book. This may be a book with a very small audience, but I enjoyed it. Beware, this is pretty technical, but not technical enough to replicate any of the algorithms described. So, you have to be someone who is interested in the nitty gritty, but not someone who wants to actually write any code.
October 17, 2024
Tough but interesting read! Somewhere between a popsci book and a textbook, it includes a lot of background on the nature and applications of the problem as well as walkthroughs of several attempted approaches from the past century of attempts to crack this mathematical puzzle. I didn’t understand 100% of it, but quite liked the parts I did!
July 9, 2022
Excellent exposition.
(But your mileage may vary of course. I suppose that having a PH.D. in a somewhat different area of graph theory did help me a bit...)
(But your mileage may vary of course. I suppose that having a PH.D. in a somewhat different area of graph theory did help me a bit...)
December 8, 2017
Traveling salesman problem is used by graph theory.
They're expressed various ICT, forexample, Google search engine, maps, earth, last fm., apple music, Netflix, Hulu, smart news, spontify, line music, Amazon recommendation etc.
There're many interesting topics in it.
Probably you will enjoy reading it.
They're expressed various ICT, forexample, Google search engine, maps, earth, last fm., apple music, Netflix, Hulu, smart news, spontify, line music, Amazon recommendation etc.
There're many interesting topics in it.
Probably you will enjoy reading it.
June 30, 2021
A tremendous introduction to the Travelling Salesman Problem (TSP). William Cook, a leading TSP researcher, gives readers detailed overviews of the different tools that have been employed in battling the combinatorial explosion that results from a salesman trying to find the shortest path between a set of destinations. The book strikes a good balance between mathematical rigor and readability.
February 11, 2018
Excellent introducing to the traveling salesman problem and nice overview of discrete optimization. Wished I had read it sooner!
December 1, 2018
Excellent book from a geek for geeks. The author of the TSP book, Williams J. Cook, is also a co-author of the Concorde program which keeps a record with solving TSP for 85,900 points.
The book contains a more readable content about the history of the TSP problem, why the problem becomes interesting for mathematicians at all, about involved people, various real-world applications (e.g. saving propellant of a telescope by NASA, testing of GPUs by NVIDIA, genome mapping), mathematical art, funny stories.
But the second part of the book is uneasy reading. Be prepared for diving into the linear and integer programming, details of planes cutting methods, introduction to Christofides, Held-Karp, Lin-Kernighan(-Helsgaun) algorithms, 2-opt, 3-opt, … k-opt, etc. Honestly, I’ve skimmed through some of these. I’ll return to them when the right time for more learning and implementation comes.
And what not, the book even tell you about the affection of Bill Gates in pancake sorting! ;)
Even though I wanted only to understand and implement the Held-Karp algorithm, the book gives me a bunch of inspiration for digging deeper and learning more. With respect to the work the author did in the field, his style is humble and joyful reading. It will serve as useful reference and inspiration in the future. A sound candidate for a personal geeky library.
Bash on regardless!
The book contains a more readable content about the history of the TSP problem, why the problem becomes interesting for mathematicians at all, about involved people, various real-world applications (e.g. saving propellant of a telescope by NASA, testing of GPUs by NVIDIA, genome mapping), mathematical art, funny stories.
But the second part of the book is uneasy reading. Be prepared for diving into the linear and integer programming, details of planes cutting methods, introduction to Christofides, Held-Karp, Lin-Kernighan(-Helsgaun) algorithms, 2-opt, 3-opt, … k-opt, etc. Honestly, I’ve skimmed through some of these. I’ll return to them when the right time for more learning and implementation comes.
And what not, the book even tell you about the affection of Bill Gates in pancake sorting! ;)
Even though I wanted only to understand and implement the Held-Karp algorithm, the book gives me a bunch of inspiration for digging deeper and learning more. With respect to the work the author did in the field, his style is humble and joyful reading. It will serve as useful reference and inspiration in the future. A sound candidate for a personal geeky library.
Bash on regardless!
May 12, 2019
Popis problému obchodního cestujícího od úplných začátků až po velice složité matematické teorie, pomocí kterých se řeší v současnosti. Doporučil bych přečíst každému, kdo se o tuto tematiku zajímá, k základnímu seznámení s možnostmi řešení. V současnosti jsme schopni rychle řešit i extrémně velké problémy pomocí různých heuristik a lineárního programování. S délkou nalezené cesty jsme schopni se dostat asi na 0,5% rozdílu od nejlepší možné. I nalezení obecného polynomiálního algoritmu by tedy nemělo nějak zásadní dopady na plánování, cenný by ale byl tento výsledek z teoretického hlediska. Nejjednodušší algoritmus přes minimální kostru grafu a perfektní párování lichých vrcholů na cestě dokáže najít maximálně 1,5x delší cestu.
Na můj vkus bylo v knize příliš mnoho historek o lidech, kteří v tomto oboru pracovali.
Na můj vkus bylo v knize příliš mnoho historek o lidech, kteří v tomto oboru pracovali.
October 23, 2022
V cz překladu dost chyb včetně chyb ve výpočtech. Viz třeba výpočty. u složitosti 1 + 1/2 log N. Gates je někdy Bill a na další stránce William. I v originále ale kniha u složitějších témat vysvětluje málo a spoléhá na to, že čtenář dobře zná teorii grafů, aby na jiném místě sklouzla k vysvětlování úplných základů. I třeba zajímavé a i pro laiky přístupné Eulerovo řešení "mostů" v Královci je popsáno dost ledabyle a nudně.
February 10, 2018
Lately I have been giving sadly low ratings to math books... This one simply lost all my interest at some point. I cannot even comment on the content, since I was bored by the writing style.
September 24, 2018
I Really enjoyed reading this book, it is a real pleasure to understand the cleverness of the partial solutions!
May 14, 2019
3.5/5.0
January 28, 2024
Interesante, muy técnico a ratos, que lo volvía un poco monótono. Pero en general útil
September 12, 2024
In my pursuit of the Traveling Salesman Problem, some of my dreams were crushed but it is a great read nonetheless.
Best read in 2024 so far.
Best read in 2024 so far.
March 19, 2018
ahahaha
October 17, 2023
I revisited this book after a gap of five years. On my first read, I found it quite captivating, and my second reading was no less engaging.
This book weaves several elements around the infamous Traveling Salesman Problem (TSP), offering:
- A rich set of trivia involving anecdotes, historical tidbits, and numerous quotes from "celebrities" in computer science and operations research. Accompanying the text are various images, graphs, and color Venn diagrams.
- A mathematical outline of the most successful methods for solving the TSP. By "solving" here, I do not mean being imaginative and inventing a heuristic that performs well only on some instances of the problem, but adhering to the formal definition of "solving": finding the optimal solution while also formally demonstrating that no better solution exists. Be forewarned: this section might not captivate everyone.
- An introduction to integer programming, covering linear programming, branch and bound, and branch and bound and cut. For those unfamiliar with these concepts, this book serves as an excellent primer, using TSP -a concept the reader becomes acquainted with- as a demonstrative tool, as opposed to conventional examples like the "diet problem" found in most textbooks. One nice advantage of TSP over these conventional problems is that it's much easier to visualize, and this book has plenty of such visualizations. Again, this portion might seem tedious to some.
- An introduction to complexity theory within a single chapter. By complexity theory, I do not mean asymptotic analysis (which most people assume to be what "complexity theory" only entails), but an exploration into the P vs NP problem and how the TSP relates to this issue. Once more, this part might not be appealing to everyone.
In conclusion, this book is a valuable resource for computer science or operations research practitioners interested in solving discrete optimization problems who can appreciate detailed mathematical exposition.
This book weaves several elements around the infamous Traveling Salesman Problem (TSP), offering:
- A rich set of trivia involving anecdotes, historical tidbits, and numerous quotes from "celebrities" in computer science and operations research. Accompanying the text are various images, graphs, and color Venn diagrams.
- A mathematical outline of the most successful methods for solving the TSP. By "solving" here, I do not mean being imaginative and inventing a heuristic that performs well only on some instances of the problem, but adhering to the formal definition of "solving": finding the optimal solution while also formally demonstrating that no better solution exists. Be forewarned: this section might not captivate everyone.
- An introduction to integer programming, covering linear programming, branch and bound, and branch and bound and cut. For those unfamiliar with these concepts, this book serves as an excellent primer, using TSP -a concept the reader becomes acquainted with- as a demonstrative tool, as opposed to conventional examples like the "diet problem" found in most textbooks. One nice advantage of TSP over these conventional problems is that it's much easier to visualize, and this book has plenty of such visualizations. Again, this portion might seem tedious to some.
- An introduction to complexity theory within a single chapter. By complexity theory, I do not mean asymptotic analysis (which most people assume to be what "complexity theory" only entails), but an exploration into the P vs NP problem and how the TSP relates to this issue. Once more, this part might not be appealing to everyone.
In conclusion, this book is a valuable resource for computer science or operations research practitioners interested in solving discrete optimization problems who can appreciate detailed mathematical exposition.
June 17, 2012
Who would have thought that determining the most efficient route for a traveling salesman would present one of the most complex--and still unsolved to this day--mathematical and computational challenges, right up there with finding the end of pi. The math herein at times gets a bit complex, but overall the book is very accessible. The RAND Corporation sponsored a prize for solving the TSP puzzle and RAND's Dantzig, Fulkerson, and Johnson in 1954 presented a 48-state TSP tour solution that has endured as one of the most valuable contributions to advancing our knowledge about the nature of complexity
March 27, 2013
An ever present dilemma for science popularization is detail vs. digestibility. This text erred on the side of detail, which is less bad than being glib. Nevertheless I felt like the text was sufficiently technical that I might as well read an OR text about the subjects in question and just get it all down.
There was one nice thing about my experience though: suddenly made me think about the fact that increasing marginal costs effectively do not confront large firms in real life, on account of the fact that they can continue to use linear programming, which of course assumes constant marginal costs on input factors.
There was one nice thing about my experience though: suddenly made me think about the fact that increasing marginal costs effectively do not confront large firms in real life, on account of the fact that they can continue to use linear programming, which of course assumes constant marginal costs on input factors.
August 14, 2014
As a mathematics teacher I found this book to be one of very few books that was qualitative enough to be readable as a recreational book and not as a textbook while being quantitative enough that I feel that I understand the actual mathematics behind the attempts to solve the problem. Outstanding work! Will motivate math students to examine this problem more deeply and rigorously.
January 20, 2013
Fantastic recreational mathematics book. Gives a great view of why people do research and how it all fits together. The author is clearly enthusiastic about this problem, and that enthusiasm is contagious. Perhaps the best popular book in operations research.
February 17, 2013
A nice treatment of a deep mathematical problem, deceivingly simple and intuitive but complex and computationally unwieldy. I really enjoyed the connection to mathematical art. The book gives some good connections to optimization and real-life examples of mathematical break-throughs.
December 14, 2012
Interesting contents, clearly and engagingly written.
Read
March 1, 2013511.5 C7719 2012
February 23, 2015
Interesting topic, but little effort is made to make the technical parts accessible, let alone interesting.
November 11, 2012
beautifully crafted book with color illustrations but the writing is not very clear.
Displaying 1 - 26 of 26 reviews