Heterogenous Resource Allocation Using Dynamic Programming

Question

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?

Answer 1

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.

• pronerd7: 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?
• D.W.: @pronerd7, see edited answer for such an algorithm.