Twenty-four years ago a 2,392-city example of the TSP was solved in a 23-hour run on a super computer to set a new world record. This same problem now solves in 7 minutes on an iPhone 4 thanks to a free app: Concorde TSP Solver!
The CONCORDE TSP SOLVER app is a powerful display of the potential to solve on mobile devices large examples of even the most difficult computational problems. This makes it an ideal tool for understanding and teaching the mathematics behind the most successful line-of-attack on the salesman problem. The colorful graphics show step-by-step how a tool called linear programming zeros in on the optimal route to visit a displayed collection of cities.
CONCORDE TSP SOLVER is a great companion to Cook’s book In Pursuit of the Traveling Salesman for general readers and mathematics students alike.
Some early reviews from Twitter:
@CompSciFact (2/5/12)
“We have an embarrassment of computational riches when we can solve traveling salesmen problems on a phone.”
@misterbrash (2/5/12)
“This unravels by University degree and hurts my brain! Solve traveling salesman problem(s) on your iPhone. In seconds.”
@ehtayer (2/5/12)
“Computational life is lush: traveling salesman app.”
@miketrick (2/4/11)
“Touring lots of cities? There’s an app for that! Amazing work by @wjcook and gang.”
Are you following PUP on Google+ yet? If not, today’s the day to add us to your circle—we’re giving away a copy of Magical Mathematics by Persi Diaconis & Ron Graham, along with a Magical Mathematics deck of cards to practice your magic tricks! Follow us by Friday to win!
Magical Mathematics reveals the secrets of amazing, fun-to-perform card tricks—and the profound mathematical ideas behind them—that will astound even the most accomplished magician. Persi Diaconis and Ron Graham provide easy, step-by-step instructions for each trick, explaining how to set up the effect and offering tips on what to say and do while performing it. Each card trick introduces a new mathematical idea, and varying the tricks in turn takes readers to the very threshold of today’s mathematical knowledge. For example, the Gilbreath Principle—a fantastic effect where the cards remain in control despite being shuffled—is found to share an intimate connection with the Mandelbrot set. Other card tricks link to the mathematical secrets of combinatorics, graph theory, number theory, topology, the Riemann hypothesis, and even Fermat’s last theorem.
We were thrilled to read Jennifer Schuessler’s terrific story on the popular phenomenon of bar lecturing (and not in an intoxicated way, but a learned way!) Check out her story here. It looks like alcohol and science is a powerful (and successful) formula.
The Press is pleased to have had the pleasure of working with the Secret Science Club as they’ve hosted talks for a handful of our science authors. In particular, I was delighted to see friend-of-the-Press Dorian Devins at the SSC getting a mention!
This anthology brings together the year’s finest mathematics writing from around the world. Featuring promising new voices alongside some of the foremost names in the field, The Best Writing on Mathematics 2011 makes available to a wide audience many articles not easily found anywhere else—and you don’t need to be a mathematician to enjoy them. These writings offer surprising insights into the nature, meaning, and practice of mathematics today. They delve into the history, philosophy, teaching, and everyday occurrences of math, and take readers behind the scenes of today’s hottest mathematical debates. Here Ian Hacking discusses the salient features that distinguish mathematics from other disciplines of the mind; Doris Schattschneider identifies some of the mathematical inspirations of M. C. Escher’s art; Jordan Ellenberg describes compressed sensing, a mathematical field that is reshaping the way people use large sets of data; Erica Klarreich reports on the use of algorithms in the job market for doctors; and much, much more.
Princeton author Persi Diaconis is one of the world’s top mathematicians and was recently interviewed on BBC Radio 4’s More or less about the new book he recently co-authored with Ron Graham, Magical Mathematics: The Mathematical Ideas that Animate Great Magic Tricks. In the interview, Persi explains the fascinating maths behind a magic trick that he developed himself, one which has even the BBC’s in-house magician baffled, until Persi explains it.
The full interview and a video of the card trick being performed can be found on the More or Less website. This is a great example of the many fun tricks discussed and explained in Magical 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.
Cook examines the origins and history of the salesman problem and explores its many important applications, from genome sequencing and designing computer processors to arranging music and hunting for planets. He looks at how computers stack up against the traveling salesman problem on a grand scale, and discusses how humans, unaided by computers, go about trying to solve the puzzle. Cook traces the salesman problem to the realms of neuroscience, psychology, and art, and he also challenges readers to tackle the problem themselves. The traveling salesman problem is—literally—a $1 million question. That’s the prize the Clay Mathematics Institute is offering to anyone who can solve the problem or prove that it can’t be done.
In his new book, MacCormick identifies the most amazing “tricks” our computers perform — things like encryption, compression, searches — thanks to algorithms. Of course, as with any “list”, there simply isn’t enough room to include every possible algorithm, so sound off below on which algorithms are the most pivotal, creative, or useful in our PCs and hand-held devices.
Featuring commentary and interviews from Princeton University Press authors, the PUP Blog is a highly respected, timely and indispensable source for learning, understanding and reflection.
I’ve just read ‘Tales of Fiscal Adjustment’ by Alesina and Ardagna, which appears to be the founding text for the idea of expansionary austerity. The level of scholarship, at least as it applies to Australia (which is their first illustration) is exceptionally poor, to the extent that it requires a rescuscitation of the ancient Internet […]
Via Mark Thoma, and drawing upon James Bullard at the St. Louis Fed, MacroMania writes: I think that Bullard makes a persuasive case that the amount of household wealth evaporated along with the crash in house prices should likely be viewed as a “permanent” (highly persistent) negative wealth shock. Standard theory (and common sense) suggests […]
Bryan Caplan has a very good post on the human capital and signalling models of education. The key point is this, under the human capital model someone who forgets knowledge is no better than someone who failed to learn the same knowledge. Under the signaling model, however, failing and forgetting are very different. Bryan illustrates: […]
Here are some 2nd-year Cooper's Hawks (birds in their first adult plumage) with retained juvenile flight feathers (the pale brownish ones). Note the lack of any grayish color and the more distinct banding of the juvenile feathers. […]
From Ricardo Hausmann: Greece will have to bring its current account deficit down to zero at some point. This can happen in two ways: either Greece exports more or spends less. Adjusting the current account by spending less would require an additional fall in GDP of 25 per cent, given that in Greece only one […]
If you're reading this blog, you probably didn't fail a lot of classes in school. But I bet that you've totally forgotten a lot of those classes. I got A's in junior high and high school Spanish, but barely speak a word of it.Now ask yourself this:How would your career have been different if you had failed all the classes you've to […]
I heard a rumor that a famous economist was asking about my book in progress, The Case Against Education. So I sent him the following email:I heard you were asking about me at the GMU dinner earlier this week. I am indeed working on a book defending the empirical importance of the signaling model of education. I'm happy to discuss my project at lengt […]
A little while ago I came across this delightful essay, On Being the Right Size, by , courtesy of the always-interesting Farnam Street blog. An essay that seems to be about biology (and for more on this see 2010′s Royal … Continue reading → […]
1. There is no great stagnation: the horizontal shower. 2. What if Star Trek had social networks? 3. The culture that is Iceland. 4. New economics blog from Phillips Exeter Academy. 5. TGS for musical instruments? 6. Profile of Scott Stern’s work on the economics of science. 7. Kristof has quite a reasonable review of […]
Twenty-four years ago a 2,392-city example of the TSP was solved in a 23-hour run on a super computer to set a new world record. This same problem now solves in 7 minutes on an iPhone 4 thanks to a free app: Concorde TSP Solver!
CONCORDE TSP SOLVER is a great companion to Cook’s book In Pursuit of the Traveling Salesman for general readers and mathematics students alike.
