09 Wish List Optimization

© Friederike Hofmann, MATH+

Authors: Max Klimm, Martin Knaack (TU Berlin)
Project: Combinatorial network flow methods for instationary gas flows and gas market problems (CRC/TRR 154, Project A07)

Challenge

Before Christmas, all children send Santa their wish list of presents they would like to receive.

Santa has prepared a bag with gifts for each child,whose size depends on how good the child has been in the past year. While filling the bag, Santa works through each child’s wish list from top to bottom. More precisely:

• Santa tries to pack the first item on the list first, then the second, and so on until the end of the list.
• Whenever an item fits in the bag, it goes in the bag; otherwise, it is not packed and Santa continues with the next item on the list.
• A set of items fits in the bag if and only if the sum of their sizes is less than or equal to the size of the bag.

Nasti, Manu, Jona, and Uli want the following items for Christmas this year, each of them bringing them a given joy:

The children know the size of each item and the joy they bring, but they do \textit{not} know how big the bag will be that Santa chooses for them. Of course, they want to maximize the total joy of the gifts in their bag. However, they have used different strategies to write their wish list. The children’s wish lists are the following:

Santa revealed to us that all the children will get a gift bag of the same size and that this size is a positive integer. Which of the following statements is correct?

Possible answers:

1. The larger the gift bag, the bigger the total joy of Nasti’s gifts.
2. The total joy of Nasti’s gifts is always at least as big as Manu’s.
3. The total joy of Nasti’s gifts is always at least as big as Uli’s.
4. The total joy of Manu’s gifts is always at least as big as Jona’s.
5. The total joy of Manu’s gifts is always at least as big as Uli’s.
6. The total joy of Jona’s gifts is always at least as big as Nasti’s.
7. The total joy of Jona’s gifts is always at least as big as Manu’s.
8. The total joy of Uli’s gifts is always at least as big as Nasti’s.
9. The total joy of Uli’s gifts is always at least as big as Jona’s.
10. None of the statements 1 to 9 is correct.

Project reference:

The project deals with capacity utilization in hydrogen networks. The above items then correspond to bookings in the network and their joy to the respective economic benefits of the hydrogen transport. Due to the non-linear gas physics and the complexity of the hydrogen network, the conditions on which items can be packed are much more complicated than in this task. How the items can be packed in a way that in addition the total pleasure is maximized is the subject of research in this project.