Welcome to the OR-Exchange, your site for questions and answers in operations research.

vote up 2 vote down
star

What is the best Christmas oriented operations research issue you have seen? I'll start off with a brief blog post I made on how far Santa and his reindeer have to travel: http://mat.tepper.cmu.edu/blog/?p=494. Have you seen other papers/posts/articles?

flag

5 Answers

vote up 2 vote down

I'll add another one. What algorithm does a string of lights 50 feet long use to get a knot right in its middle?

link|flag
vote up 2 vote down

Another possibility: The Secret Santa's Problem solved via constraint programming by Hakan Kjellerstrand http://www.hakank.org/constraint_programming_blog/2009/12/merry_christmas_secret_santas.html

link|flag
vote up 1 vote down

Here is a variant of the Secret Santa problem: http://www.hakank.org/constraint_programming_blog/2009/12/1_year_anniversary_and_secret_1.html. The objective is to maximize the "Secret Santa distance", i.e. to previous Secret Santa assignments.

link|flag
vote up 0 vote down

With all those Christmas cards being sent to people all at the same time, I guess somebody at USPS is going crazy.

Sounds like multiple instances of the TSP problem with capacity constraints.

link|flag
vote up 0 vote down

I suppose there is a knapsack problem in there with Santa's toy bag and all of those gifts.

link|flag
A knapsack model would imply that you only get what Santa could fit, which leaves a lot of ponies unexplained. I think it's more of a packing problem -- in what order do you load the bag so that (a) the next present to be delivered is near the top (trivial if you know the route) and (b) the ponies don't crush any of the fragile stuff (NP hard, where NP = Number of Ponies). – Paul Rubin Dec 28 at 19:49

Your Answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.