In Pursuit of the Traveling Salesman

William J. Cook

Why I looked at this book

We hear a lot of the P vs NP question, and it's easy to get the impression that NP problems are generally intractable, but problems like that of the Travelling Salesman do need to be solved in real world applications. I'm hoping that this book will tell me more about the progress which has been made in tackling the TSP, and possibly what the relevance of this is to P vs NP in general.

First impressions

The book starts by telling of a competition in the 1960's to find the shortest tour round 33 cities in the USA. Some people had got the idea that it was impossible, but there were several correct entries, and although no-one proved that they had an optimal tour, there was certainly the expertise to do so - although it might have taken a few weeks. So far the book is easy to read, and I hope that it will deal with later developments in the TSP without getting too much more challenging.