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 d 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. -- "Math Less Traveled"

# 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 d 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. -- "Math Less Traveled"

Compare

4out of 5Nathan Schwartz–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.

4out of 5Ami Iida–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.

5out of 5Walter–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 prob 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!

5out of 5Vilém Zouhar–Well balanced popular science book on TSP. Even though the solution is nowhere in sight, its definitely important to raise awareness of theories surrounding TSP in the community of science supporting people. Reading requires introductory knowledge of computer science and discrete mathematics.

5out of 5Martin Krauskopf–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 st 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!

4out of 5Dalibor–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 n 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.

4out of 5Gabriela–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.

5out of 5Odo–3.5/5.0

4out of 5Michiel–Excellent introducing to the traveling salesman problem and nice overview of discrete optimization. Wished I had read it sooner!

5out of 5Luciano Elementi–I Really enjoyed reading this book, it is a real pleasure to understand the cleverness of the partial solutions!

5out of 5Jovany Agathe–ahahaha

4out of 5John–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 en 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

4out of 5Muhammad al-Khwarizmi–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 th 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.

4out of 5David–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.

5out of 5Alec Myres–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.

4out of 5Michael Trick–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.

4out of 5Chris–Interesting topic, but little effort is made to make the technical parts accessible, let alone interesting.

4out of 5monkeyelf–Interesting contents, clearly and engagingly written.

5out of 5Mills College Library–511.5 C7719 2012

4out of 5Pablo Navarro–4out of 5Nathan Bingman–5out of 5Andrei–4out of 5Andreas–4out of 5Mike Greenfield–5out of 5Jack–4out of 5Treasa Lynch–5out of 5Ozan Erdem–5out of 5Will–4out of 5Ints–4out of 5Nick–