I’ve had several requests to explain the mathematics behind the pictures I’ve generated for this blog. I’m flattered by your interest and hope I can both slake and pique your curiosity with this post, which I may refer back to and update in the future.(The formatting for this may not…

Have you heard of GIMPS, the Great Internet Mersenne Prime Search?

They recently found the biggest prime ever discovered (again). I (or my computer) found that M(59551223) and M(59550011) aren’t prime. Yay?

Definitely not, there are lots of us! (We just don’t get out much…)

I would suggest looking under the ‘math’ or ‘maths’ tags but they are mostly full of homework haters.

If you’re looking for suggestions:

are some good ones.

Also, the ‘mathematics’ tag seems to have less homework haters and more interesting things.

Here is a link [1] to the latest research on the traveling salesman problem (TSP). The TSP [2] involves visiting a set of cities using the shortest path possible while visiting each city only once (e.g. finding the shortest route). Recent research has demonstrated that by using the Christofides’ algorithm, good approximations to an solution (at most 50% of the true shortest route) are possible [3]. Solutions to the TSP can be applied to a wide range of problems, including logistics, phylogenetic analysis, and power grid optimization.

[1] New directions in TSP research (website hosted by Georgia Tech). The pictures above show a TSP tour on a set of points resembling “Mona Lisa”. The bottom picture is representative of a more typical TSP problem (very large set size).

[2] The TSP is an NP-hard graph optimization problem, which requires innovative algorithmic solutions such as the Christofides algorithm or ant colony optimization (ACO). An example from the ACO literature:

Dorigo, M. and Stutzle, T. Ant Colony Optimization: Overview and Recent Advances. In “Handbook of Metaheuristics”, M. Gendreau and J.-Y. Potvin eds, International Series in Operations Research and Management Science, Springer, Berlin (2010) Chapter 8.

[3] Klarreich, E. Computer Scientists Find New Shortcuts for Infamous Traveling Salesman Problem. Wired Science, January 30 (2013).

Interesting article, but Christofides’ algorithm (or its analysis) is not a novelty: What’s actually new here is the discovery that it can be improved, if only by an epsilon (so far).

Sunrise.

I am more proud of the fact that I got up at that time of day than of the actual photo, but it did look pretty great.