Computational Christmas

Dec 3

Traveling salesman

Helmi leaned over a sprawling map of the world, dotted with blinking lights marking every delivery point. Santa’s Christmas route was the ultimate optimization problem: a traveling sleigh salesman’s dream—or nightmare. Last year, the digital system running Dijkstra’s algorithm had nearly overheated, struggling to compute the shortest path in time. “Too slow,” Helmi muttered, shaking his head. This year, he had a new plan. Using partial differential equations to model the sleigh’s flow across the globe, he set up the peppermint annealer, an analog device that minimized travel time by finding the optimal energy state. Helmi watched as the device’s brass levers clicked and shifted, aligning pathways like rivers finding the easiest course. Within moments, the route emerged—swift, precise, and ready for the sleigh. Helmi grinned. “Take that, digital bottlenecks.” The reindeer stamped their approval, eager to test the new plan.

In order to understand how the analog approach is superior, first let's do the math of existing route planning: In 2014, Santa had to visit 1.8 billion households where in 2024, it is now 2.1 billion households (one billion = 109). The machines so far are running an algorithm approximatively solving TSP within a 𝒪(n2) runtime, with 𝒪 being the Landau notation and n the number of households. In 2024, how much longer does it take Santa to visit all households, relative to 2014?

Vote is open. Please register first.