# Heterogenous Resource Allocation Using Dynamic Programming

I'm working on a resource allocation problem, where there are $$n$$ different Items and $$m$$ different tasks ($$n\geq m$$). Also, The profit of assigning subset $$I=\,(\, |I|\leq n)$$ of items to task $$j$$ is calculated by $$f(I;j)$$. If no item is assigned to task $$j$$, then the profit is calculated as $$f(\emptyset;j)$$. The objective is to find the subset of items ($$I_j$$) for each task $$j$$ to maximize $$\sum_{j=1}^nf(I_j;j)$$. $$maximize \sum_{j=1}^nf(I_j;j)\\ s.t. |I_j|\leq n , \forall j \in \{m\}$$

All items should be assigned, and each item should be assigned to one and only one task. Of course one can think of a brute-force search with the complexity of $$O(m^n)$$. Could there be a dynamic programming (DP) approach with less complexity?

You can't avoid an exponential running time. It takes $$m \cdot 2^n$$ space even to write down $$f$$, and any correct algorithm needs to read every entry of that, so any correct algorithm must take at least $$\Omega(m \cdot 2^n)$$ time.

It is possible to solve the problem in $$O(m \cdot 4^n)$$ time, using dynamic programming. In particular, let $$A[S,j]$$ be the lowest-cost assignment to tasks $$1,2,\dots,j$$ using the items in $$S$$ (every item in $$S$$ is used exactly once). Then we obtain a recurrence relation

$$A[S,j] = \min \{A[T,j-1] + f(S\setminus T;j) \mid T \subseteq S\}.$$

Finally, we can fill in the entries of $$A$$ using dynamic programming, by first filling in all of $$A[\cdot,1]$$, then all of $$A[\cdot,2]$$, and so on.

A more careful analysis shows that this dynamic programming algorithm actually runs in $$O(m \cdot 3^n)$$ time. I am not sure whether it is possible to solve it in $$O(m \cdot 2^n)$$ time.

• Yes, that's exactly what I was thinking. However, usually in my case $m>n$, and n is very large which means $m^{n-1} << 2^n$. So, I think it may make sense to use DP in this case. Unfortunately, I am somehow new to DP problems. Do you have any guidelines for a DP approach to this problem? Commented Nov 15, 2022 at 21:07
• @pronerd7, see edited answer for such an algorithm.
– D.W.
Commented Nov 15, 2022 at 22:26