Where next?

In Pursuit of the Travelling Salesman: Mathematics at the Limits of Computation by William J Cook

This is one of those maths books that describes the problem, and then tells the story of the various historical approaches to solving it. The story is fascinating, and in the pre-computer days involved massive amounts of hand calculation using clever tricks to prove lower bounds for various instances of the problem.

Along the way we learn about the P!=NP conjecture, and also learn about the simplex method and integer programming which can be used as a way to get strong lower bounds for various for travelling salesman problems (using so called control zones).

A good interesting read.

Advertisements
This entry was posted in Books. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s