Perfect Allocation of Items (to Clones)

Input: A set of n items and a set of agents with identical preferences over the items encoded as utility values.

Output: Allocate the items to the agents such that everyone obtains the same sum of utilities.

1.1 Describe a dynamic programming algorithm that solves Perfect Allocation of Items for three agents in pseudo-polynomial time. (This means that the running time bound may depend polynomially on the number n of items and on the maximum utility value umax.) Can you do it in time O(n (n umax) 3 ) or even faster when assuming that all items must be allocated?

1.2 Can you develop an polynomial-time algorithm that works also when not all items must be allocated

1.3 Try to extend the algorithm for the case where agent do not have identical preferences. What has to change?

Santas Problem

The World Santa Claus Organization (WSCO) wants to organize the distribution of gifts next Christmas. The organization consists of n santas and m elves who are responsible to bring gifts to k kids. Each santa i has a list Ki of kids he can reach on Christmas day and a list Ei of elves that can produce gifts for him. Each kid can receive at most one gift and each elf can produce at most one gift. The WSCO wants to find an assignment of santas to kids and elves that maximizes the number of kids that get a present. However, because of the efforts of the Santa Clause labor union, every santa is only allowed to be assigned ` kids.

2.1 Model the described problem as a network flow problem