1
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – pronerd7
    Commented Nov 15, 2022 at 21:07
  • $\begingroup$ @pronerd7, see edited answer for such an algorithm. $\endgroup$
    – D.W.
    Commented Nov 15, 2022 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.