Christmas 2015: Advent calendar of research

In the run up to Christmas I have been posting each day that is (loosely) related to Research and Knowledge Exchange, and is also Christmas related.

I thought it worthwhile just summarsing them here so that you can take a look at them from from one easily accessible place.

  1. Deck the halls with research stories
  2. The Christmas Present Problem: It’s Hard – NP-Hard
  3. Packing Santa’s Sleigh
  4. How will Santa deliver all those presents this Christmas?
  5. The 12 days of Pascal’s triangular Christmas
  6. Brian Cox: Can Santa travel faster than the speed of light?
  7. Five tricks retailers will use to make you shop this Christmas
  8. Problems with your wi-fi? It could be your Christmas lights!
  9. Santa is really a Travelling Salesman
  10. How do Christmas TV adverts keep your attention
  11. Have a go at solving this Christmas cryptographic problem
  12. How does electricity usage change on Christmas day?
  13. Is your oven big enough for the turkey
  14. How will (retail) Christmas compare to 2014?
  15. Should shops open on Christmas day?
  16. Could your Christmas decorations be a hazard to planes?
  17. How Christmas lights helped guerrillas put down their guns
  18. Program your own Christmas Tree
  19. Festive spices and their intoxicating history
  20. What makes a Christmas gift good?
  21. The appeal of the Christmas song
  22. Buying Christmas presents is a real dilemma
  23. Wisdom of the Crowds at the Graduate School Christmas Party
  24. Magical Mathematics: The Mathematical Ideas That Animate Great Magic Tricks

The Christmas Present Problem: It’s Hard – NP-Hard

Santa Clause (downloded from Google 07 Dec 2014, labelleed as free to reuse)
Santa Clause (downloded from Google 07 Dec 2014, labelleed as free to reuse)

As Christmas approaches, many of us are faced with the annual problem of who to buy presents for, how much to spend, what presents to buy and how to be fair to everybody.

Is this a tough problem to solve? Perhaps some science will help?

Let’s try and state the problem a little more precisely, and make it simple by assuming that we are buying presents for just one person. That does not detract from the more complex problem, especially if we establish that buying presents for one person is hard.

  • You have to buy presents for just one person; your daughter
  • You have a certain budget; an amount of money that you cannot excced
  • You have a list of gifts that your daughter would like (we are assuming that she has been good so Father Christmas is willing to leave these gifts)
  • To make life easier, you have given your daughter 100 points, and told her to assign a certain number of points to each item. The more points she assigns, the more likely she is to get that gift. For example, if she assigns all 100 points to just one gift (and zero points to the other gifts), then she is likely to get that gift. But if she assigns equal points to all gifts, then she is equally likely to get each item, but not all of them, as the total costs of the gifts bought cannot be more tha the overall budget.

Your task is to buy as many presents as possible which maximizes the number of points, whilst staying within your budget.

How difficult do you think it is to find a solution to this problem so that you daughter gets the best possible gifts such that there is not another selection of gifts that has a higher overall points value?

In fact, it is surprisingly difficult, especially as the number of available presents (and people you are buying for)  increases.

Pile of wrapped presents: (CC 3.0)
Pile of wrapped presents: (CC 3.0)

The problem is the so called Knapsack Problem, so named as you have knapsack which can carry a certain weight (your budget). Each item has a weight (cost of each item) but also a value (the number of points). You have to fill the knapsack, maximizing the value, but keeping the sum of all the weights less than the capacity of your knapsack.

Or, in terms of the Christmas Present Problem, you need to buy the best selection of presents to give the maximum number of points, while staying within your overall budget.

The Knapsack Problem is known to be an NP-Hard problem. These type of problems do not, as yet, have any efficient algorithm that can produce the optimal solution in reasonable time. At least for large sized problem instances. Hopefully, you can still give your daughter the best set of presents!

In fact, if you can find an efficient algorithm you could win one million dollars.