A kind of generalised assignment problem where we minimise error relative to a goal "weight"/"value" - how to solve it?

Question

I apologize if I did not use the terminology entirely correctly in the title. This problem seems to me quite similar to an assignment problem and likely something that occurs in real life in business.

The problem:

• In this problem, we have a set of assets (in the economics/finance sense) $\left\{ a_i \right\} $ with values $\left\{v_i\right\}$ (always positive) respectively, and a set of people $\left\{p_j\right\}$. For each person, we have a (positive) value $\left\{g_j\right\}$ (respectively), which is our goal for the total value we want to assign to this person.
• We can assign multiple assets to a single person but cannot assign an asset to more than one individual or divide an asset in any way. Given such an assignment $f: a_i \mapsto p_j$, we can calculate the total value assigned to person $p_j$, call it $T_j(f)$, as the sum of the values of all assets assigned to person $p_j$. We wish to find an assignment $f$ which minimizes $\max_j(|T_j(f) - g_j|)$, i.e., we don't want to have a large error for even a single individual.

I'll describe my questions and then my current attempts/idea.

Questions:

1. Does this problem have a name, either with the current objective function I mentioned or maybe minimizing something else, e.g., the sum of absolute errors or squares of errors?
2. The main question is finding an efficient way to solve this. I am looking to solve it with 10 people and 60 assets, i.e., considering $10^{60}$ possible assignments. So a brute-force method will not work.

My ideas:

1. my only idea, except for going through all options, is to set some maximum value for that error I mentioned, $\max_j(|T_j(f) - g_j|)$, and this allows to prune the search tree (the search-tree I am thinking of is one where the first level is the assignment of asset $a_1$ to each of the persons, the second level is the assignment of $a_2$, etc.) whenever the total value for even a single individual goes above that. This should do a lot of pruning, and I know from experience with my datasets that, in most cases, it is possible to find a solution with a relatively small error (an error of the type I described).

But this pruning method seems not to be that fast/efficient.

Answer 1

The problem you describe is strongly NP-hard since it generalizes the 3-PARTITION problem. Hence you can expect no efficient algorithm for it, unless P = NP.

To see that it generalizes the 3-PARTITION problem, take an instance S of 3-PARTITION that is composed of 3m positive integers summing to mT. Now consider the following instance of your problem: there are m persons, each with a goal of T. There are also 3m assets, one for each positive integer in S, with the corresponding value. Then you can find an assignment with cost zero (that is, meet exactly the goal of each person) if and only if the 3-PARTITION instance has a solution.