Better shopping through math

-A A +A

Your new store is very imposing, but there is a problem for many of us who have limited time or energy. This concerns the vast distances that must be covered to complete even a modest shopping list.

On foot, we find ourselves exhausted, but even with a cart it is very challenging. Of course, one could stop for a beer or Starbucks espresso to refresh, but the total time is increased accordingly.
The Traveling Salesman Problem (TSP) is one of the most famous in mathematics: How can one visit all the cities in a region in the shortest
time without repetition?
As Wikipedia puts it: “The most direct solution is to try all permutations and see which one is cheapest.”
The running time for this approach lies within a polynomial factor of O(n!), the factorial of the number of grocery items, so this solution becomes impractical even for only 20 grocery items.
However, the Held–Karp algorithm solves the problem in time O(n^2*2^n).
Many free programs are listed in the article. It would be a great service to provide this capability on your carts, and/or have printouts available at suitable stations.
Of course, we would have to input our grocery list ourselves. Even a program limited to food items would be an immense service.
We could thereby halve our shopping time according to a mathematical estimate. We believe this would perform a great service to the community, and could put Los Alamos on the map.

John Dienes
Los Alamos