Santa Claus’s Nested Traveling Salesman Problem

Avatar

James Hanley

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

Related Post Roulette

4 Responses

  1. Avatar ppnl
    Ignored
    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
    Ignored
    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
      Ignored
      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
    Ignored
    says:

    It appears your tax dollars are safe, Santa tracking is funded by corporate sponsors.
    http://www.noradsanta.org/en/faq.html#f21Report

Leave a Reply

Your email address will not be published. Required fields are marked *