Santa Claus’s Nested Traveling Salesman Problem


James Hanley

James Hanley is a two-bit college professor who'd rather be canoeing.

Related Post Roulette

4 Responses

  1. Avatar ppnl says:

    I’m afraid you have it all wrong. Santa being supernatural can easily solve traveling salesman problems. The largest computers in the world cannot solve even fairly small instances of the problem. It turns out that better solutions to these problems have massive numbers of applications affecting everything from road networks to national security.

    So what the NSA did is to carefully place a network of “good children” in a way to map to a traveling salesman problem they need solved. They then use NORAD to track him and read off the answer. Better national security through programming Santa.

    May you be touched by his noodly appendage in this season of the red and green sauce.Report

  2. Avatar KenB says:

    Hmm, I don’t see the nesting – there’s no requirement within a city that he return to his starting point.Report

    • Avatar ppnl in reply to KenB says:

      Technically true but the requirement to return does not change the computational complexity. In fact a problem of one kind can easily be converted into a problem of the other kind. So Santa can still act as our oracle.Report

  3. Avatar Matty says:

    It appears your tax dollars are safe, Santa tracking is funded by corporate sponsors.